The total entropy actually increases, as the molecular cloud shrinks under gravity.
It may seem that as the molecules are getting closer, they are more ordered, which means less entropy. That is however only one part of the process. The second (important) part is: when the molecules are closer, they also have higher kinetic energy (since they descended into lower gravitational potential). So the gas is getting hotter, as it shrinks.
The increase in temperature of the gas is increasing its entropy, because the molecules occupy more momentum space. This increase in entropy via temperature is bigger than the decrease in entropy via the shrinking itself.
Later on, the hot condensed gas (or hot planet) radiates the heat into the space and cools down. You end up with a cold planet which indeed has lower entropy than the original gas cloud, because it is no longer hot. But the entropy increase was carried away by the radiated photons. So in total - entropy of the universe increased (the radiated photons are out there somewhere).
You can find some more detailed discussion of this topic on the excellent web page by John Baez or here.