I haven't seen this documentary, but somewhere along the line from the initial concept for the program to the question you submitted, things got turned upside down! Read the Wikipedia article about solar system formation and that should clear up a lot of things. It serves as a general reference for what follows.
But the short answer is: the dust was there all along, from the beginning of the process that created the solar system, ready to create big giant planet cores.
The collapse of the part of the giant molecular cloud (GMC) that created the solar system happened more than 9 billion years after the big bang. In between, 3 or 4 generations of stars lived out their lives and seeded the interstellar medium with remnant gas (lots of hydrogen and helium) and heavier elements created by nucleosynthesis. That's where the dust came from, and that new and leftover material is what created the GMC in the first place. The process that created the solar system was not going through its very first iteration! Before the first generation of stars (after the big bang) went supernova there was precious little stuff to make dust out of.
The dust in the GMC consisted of a wide range of elements and minerals, including metals, silicates and other rock-forming minerals, and very cold grains of what we would call ices: water, carbon monoxide, methane...lots of stuff that at temperatures in the tens of Kelvins (-200 to -260 C) is frozen into solids. The dust and ices were maybe 2% of the mass of the GMC. The rest was hydrogen and helium, and a little lithium left over from the big bang.
There are two competing theories attempting to explain how you get from the swirling protoplanetary nebula generated during the GMC collapse to giant planets like Jupiter and Saturn. One is the core accretion model, which says that before you can accrete significant amounts of hydrogen and helium you first have to accrete a "rocky core" (more about that later) to a mass whose gravity will pull in those light gases ("hydrodynamic collapse") from the nebula and prevent their subsequent escape when temperatures increase. Then this core can rapidly pull in the hydrogen and helium from the nearby parts of the nebula, and build the huge gas balls we see today. So you have to build the core from "rocky" materials first.
The other competing theory is the nebular instability model, which says that flow instabilities in the protoplanetary nebula are sufficient to produce local density enhancements (essentially compression) sufficient to generate a gravity field that initiates hydrodynamic collapse without a rocky core. This model would eventually generate a dense core via differentiation, where all the heavier constituents sink to the center.
The two theories predict different masses for the cores. The core accretion model predicts a large core, while the nebular instability model predicts a smaller one. Results from Cassini and Juno appear to favor the core accretion model.
So a fairly massive core (very roughly ten Earth masses or so) accreted first, then the gas accreted onto that.
Now, about that "rocky" core. The dust that created it indeed had a lot of rock-forming minerals in it, along with lots of other stuff, like ices and notably metals. The metals, mostly the iron and nickel that are abundant supernova products, are generally denser than the rock-forming minerals, so during differentiation at very high temperatures they would sink to the center. The "rocky core" would itself have a metallic core! The ices, in gaseous form at these elevated temperatures, would migrate to the surface, and before the core had accreted to gas-keeping size they would be lost to space.
Accretion of a planet the size of Jupiter or Saturn converts a huge amount of gravitational potential energy to heat, and more heat is provided by the decay of radioactive elements in the GMC mix. So the cores of those planets are really hot, in the case of Jupiter in the 15,000 - 20,000 K range, far hotter than the sun's photosphere! At those temperatures and pressures these "rocky minerals" aren't only not solid, they're not liquid, either—they're above their critical temperatures. Yes, they are very dense, but calling the core "rocky" doesn't mean it is solid!