Stars are mostly hydrogen and helium. The presence of small amounts of other elements does change their luminosity, and their spectra. The heavy elements were formed in other stars.
After the big bang there was a short period in which the conditions were right for hydrogen to fuse into helium. The conditions were not suitable for any heavier elements to form, the state of the universe right after this time was about 3/4 hydrogen, 1/4 helium.
After some time clouds of hydrogen and helium began to form (around clumps of dark matter) and inside some of these clumps, smaller clouds collapsed to form the first generation of stars. These were large and they had no elements other than hydrogen and helium. These stars produced in their cores heavier elements like Carbon and Oxygen, and when they had reached the end of their lives, being big stars, they exploded in supernovae, and these elements were returned to the interstellar space, along with other heavier elements that were formed by the supernova.
The next generation of stars formed from a mixture of hydrogen, helium and the heavier elements formed in the first generation. These stars still had less heavy elements than modern stars, but were more like normal stars. Some of these stars are still around, they are known as Population 2 stars. They are found mostly in globular clusters http://hyperphysics.phy-astr.gsu.edu/hbase/Starlog/pop12.html.
After the population 2 stars had lived their lives and died, either in a supernova or in a planetary nebula, elements that had been made in their cores was returned to the intersellar space, futher enriching it with heavy elements. It was from one of these clouds, seeded with elements from stars that had gone before it, that the sun and the solar system formed.
This is why Carl Sagan says We are star stuff.