Stars are divided (this is only an approximate distinction) into Population I, Population II and Population III. Population I stars are the relatively young stars like the Sun that we see around us today, while Population II are older stars that have a low but non-zero metal content (in this context a metal is any element heavier than Helium i.e. those elements synthesised in stars rather than the Big Bang). Population III stars have never been observed: they are the hypothetical first generation of stars that formed from the primordial hydrogen/helium mixture left by the Big Bang.
Population III stars are believed to have formed the first metals then gone supernova and dispersed them into the interstellar gas. The next generation of Population II stars inherited these metals, which is why we see them in the stars spectra but at low levels. The Population II stars in turn generated the higher levels of metals that we see in Population I stars like the Sun.
The question is whether the metal concentration left behind by the Population III stars was high enough to form rocky planets, and I don't think anyone has a precise answer. I found quite a nice article discussing the history of planet formation, but the authors don't risk giving estimates for the formation of the first planets, though they do say:
A planet as massive and dense as the Earth could only form once stars and supernovae had enriched the gas with an abundance of heavy elements that is at least 10 percent that in the Sun
Incidentally, although we have never directly observed a Population III star it's believed that these stars were enormous compared to most stars today, and their deaths created gamma ray bursts that we can observe. In particular GRB 090423 may have come from a Population III star as it happened about 13 billion years ago.
The oldest star know to have planets is HIP 11952 (well, it was when I last looked - this is a rapidly changing area). However this star has a metallicity only 1% that of the Sun, and the two planets found are more like Jupiter than the Earth. Whether the system has, or had (the two hot Jupiters may have ejected them) rocky planets we can't say.
One of the oldest known galaxies with a metallicity high enough to form terrestrial planets is a quasar that formed about 2.8 billion years after the Big Bang. Obviously we'll never know if any of the stars in that galaxy actually have terrestrial planets.