The fluctuations in the CMB you refer to are over-densities and under-densities in the matter distribution of the early universe (among other things). An over-density is where a region of space has a more dense distribution of matter than the average value of the rest of space. Quite literally, the density is over the background value.
If the mass distribution of the universe had been perfectly uniform, there would be no net gravitational force on anything because an equal amount of mass in all directions would have a net cancelling effect. However, when you have over- and under-densities, the unequal distribution allows for there to be local centers of gravity. Remember that gravity travels at the speed of light. Also remember that inflation (which happened long before recombination) increased the universe in size by a factor of about $e^{60}$ in $10^{-34}s$. So pretty much the only things an object could feel a gravitational force from after that were those that were within the radius that light could have travelled after inflation. This means that at $380,000$ years, only things up to about $380,000$ light years away could have any influence on something (That's a region a few galaxies across). If these small regions happened to have more mass clumped in one area than another (they could be on one side of the "hill" of one of the large over-densities seen in the CMB, for example), matter would gravitate towards those centers. Obviously, the matter within a few light years would reach the gravity centers before the matter thousands of light years away, so what you find is that small bodies began to form in the over-dense regions.
These first small bodies may not have had enough mass to collapse into stars, but as time went on and the gravitational sphere of influence extended outward, they at least formed local cores within larger over-dense regions. As more matter fell into each system (and some bodies would also fall together and become one), eventually they became big enough to form stars.
The formation of the first stars at 50 million years also meant that now the influence of gravity extended even further, to over 50 million light years. With this, larger patterns in the density of matter emerged; the center of gravity of an overdense region would shift in some cases. This means that the stars and other bodies also began to fall together around these centers and form stellar systems.
As time goes on, this process continues with the gravitational influence extending further and further, revealing more and more of the shape of the over- and under-densities in the matter distribution to the objects inside them. Stars and basic groups of stars fell together to form protogalaxies ("proto-" can translate as "baby"). Protogalaxies eventually fell together to form galaxies, which then formed galaxy clusters, superclusters and (at what is currently the largest scale) galactic filaments.
Of course, don't get the idea that it's just Hydrogen and Helium floating around that caused all the gravity to make the first stars fall together. Dark matter was extremely important. It provided most of the mass in over-densities and really and truly is the seed for the gravitational collapse into all the interesting objects that came after.
So to answer your questions, gravity made the first stars form after recombination. And you're right, the hot spots in the CMB are too large to have formed directly into stars, but thankfully gravity isn't instantaneous and it travels at the speed of light, only small regions could communicate with each other at first, which allowed small objects to form first and allowed stars to form as the gravitational influence extended outwards. Thus, small-scale structures formed before large-scale ones and the many gravitationally bound structures we see in the universe today were able to naturally form.