When did the elements for forming planets first form after the Big Bang?

Within 1 billion years or less.

As astronomers continue to observe more distant galaxies, they are discovering that galaxies with 'solar abundances' seem to be still detectable even at redshifts near the limit of what they can spectroscopically study. Evidently, the first generation of massive stars to form a few ten's of millions of years after the Big Bang, were able to enrich the interstellar or intergalactic medium to nearly solar abundances very quickly. It would then have been possible to form the first planets within a few hundred million years after the Big Bang!

Science fiction stories that feature alien civilizations that are billions of years old may not be too far from reality afterall!