I'll answer this from a Western tradition, as I am not informed about Eastern and other cultural astronomical traditions.

People have distinguished between planets and starts since prehistoric times, but as you correctly imply, the distinction concerned how they moved about the sky rather than their material composition. They observed that most of the stars stayed in the same position in relation to one another, but a few moved in relation to one another. The most spectacular of these were the "evening star", the first bright star that appears after sunset, and the "morning star", the last start to disappear in the morning. As the evening star and the morning star never appear at the same time of year, people figured out by early historical times that they were actually the same object, always appearing in the vicinity of the sun, but sometimes leading and sometimes trailing. This object was given various mythological associations, with Lucifer, Aphrodite, Venus, and other gods and goddesses.

People were also aware of four other planets which moved relative to the "fixed" stars, and called these the "wandering" stars - Mercury, Mars, Jupiter, and Saturn. They also knew that these planets traveled on nearly the same path in the sky as the sun and moon, the great circle known as the ecliptic, offset about 23 degrees from the equator. Unlike the sun, the planets did not move in a steady progression along this ecliptic, but moved in a "two steps forward, one step back" motion that must have seemed pretty erratic to early astronomers. The basic model started to form in the near East and ancient Greece that the stars comprised a series of rotating, transparent, spherical shells around the earth, with one object fixed to each shell, except for the outermost shell which had all of the fixed stars attached to it. This model was given mathematical treatment and reached its pinnacle with Claudius Ptolemy, the Greek astronomer who wrote in the second century AD and had a fully realized model based on compound circular motion.

Now, as to the composition of the starts and planets, Aristotle proposed that they were made not of fire but of an even lighter substance called "aether", the fifth element after earth, water, air and fire. The Latin translation for fifth element was "quintessence".

This was generally held to be correct until the early scientific revolution, when Kepler might have been the first to propose that the planets were subject to the same laws of physics that governed the motion of bodies on earth, and thus could be made of the same materials that we find on Earth. Around the same time, Galileo observed the phases of Venus, proving that Venus shone not with its own light but with reflected light from the Sun.