How did Einstein come the conclusion that nothing can travel faster than the light in vacuum?
We reach this conclusion because we believe in causality: certain physical processes are observed to happen always in a certain order, never otherwise. For example, I have never eaten boiled eggs in my existence on this planet without my having to cook them first.
Before I go further, the correct rendering of your statement is that no causal link from event $A$ to event $B$ can lie outside $A$'s future lightcone, often stated "no signal can propagate faster than $c$". See my answer here where I show that certain processes can travel at faster than $c$ if there is no causal relationship between the events within the process. The travel of a material object you refer to is just a special case of a process whose events are causally linked.
Now to the rest of my answer: we postulate that the order between my cooking my eggs and my eating them is not changed when one observes these processes from relatively moving frames: there is no inertial observer moving relatively to me whose motion causes them to see me eating my eggs before I cook them. This is a crucial point once one derives the Lorentz transformation, because the Lorentz transformation shows that there is a relativity of simulteneity. Different, relatively moving observers do indeed observe different before/after time relationships between certain events. So how do we save our notions of causality?
We postulate that causal links cannot travel faster than $c$. For example, the link between my cooking my eggs and my eating them is (1) directed forwards in my time (pointing to my future) and (2) lies inside my future light cone. As long as this inside-my-future-lightcone condition is fulfilled, the basic properties of the Lorentz group guarantee that a boost cannot change the order of events linked by such relationships, even though it does change the time and space co-ordinates of those events.
There are other ways to motivate no-faster-than-light travel: for example, that the energy required to accelerate something with nonzero restmass to $c$ would be infinite. However, the upholding of causality is the overarching and most forceful motivation: there is no way to uphold the observed orders of events within a process if any pair of events on that process's worldline lie outside each others' future/past lightcone. If we believe in causality, no faster than light signalling is an inescapable conclusion.
In 1905 Einstein postulated that the speed of light is constant (more precisely, independent of the speed of the light source). I haven't seen a text where he infers from his postulate that nothing can travel faster than light.
As for the postulate, Einstein took it from the ether theory, even though in 1887 (prior to FitzGerald and Lorentz advancing the ad hoc length contraction hypothesis) the Michelson-Morley experiment had unequivocally proved that the speed of light does depend on the speed of the light source:
http://books.google.com/books?id=JokgnS1JtmMC Banesh Hoffmann, Relativity and Its Roots, p.92: "There are various remarks to be made about this second principle. For instance, if it is so obvious, how could it turn out to be part of a revolution - especially when the first principle is also a natural one? Moreover, if light consists of particles, as Einstein had suggested in his paper submitted just thirteen weeks before this one, the second principle seems absurd: A stone thrown from a speeding train can do far more damage than one thrown from a train at rest; the speed of the particle is not independent of the motion of the object emitting it. And if we take light to consist of particles and assume that these particles obey Newton's laws, they will conform to Newtonian relativity and thus automatically account for the null result of the Michelson-Morley experiment without recourse to contracting lengths, local time, or Lorentz transformations. Yet, as we have seen, Einstein resisted the temptation to account for the null result in terms of particles of light and simple, familiar Newtonian ideas, and introduced as his second postulate something that was more or less obvious when thought of in terms of waves in an ether. If it was so obvious, though, why did he need to state it as a principle? Because, having taken from the idea of light waves in the ether the one aspect that he needed, he declared early in his paper, to quote his own words, that "the introduction of a 'luminiferous ether' will prove to be superfluous."
http://philsci-archive.pitt.edu/1743/2/Norton.pdf John Norton: "The Michelson-Morley experiment is fully compatible with an emission theory of light that CONTRADICTS THE LIGHT POSTULATE."
Not sure about Einstein, I'd better speak for myself!
Relativity theory says, that it's not always possible to tell which of two events occurred earlier than the other. It's counter-intuitive, but does not lead to any paradoxes.
Wait! I'll give you a paradox! Yesterday I checked my mailbox, today I am going to put a letter into it. If for someone the "put letter into mailbox" event happens before "check mailbox", he would be able to take the letter as soon as I put it into mailbox and put it back just before I check it, so effectively I'll send a letter to myself into the past! Isn't it a paradox?
This time-travel paradox happens only if it is possible to travel faster than light. If I am traveling slower than light and some event 1 happened to me before event 2, these two events would happen in this order (first event 1 than event 2) in all the systems of reference which are moving slower than speed of light.
As soon as anyone finds a way to send some information faster than a speed of light, it would become possible to send the information back in time.