In Ptolemy and Copernicus' systems, the stars were believed to rest upon a single plane, the 'celestial sphere'. People thought they were all the same distance away from earth. Kepler's insight was about the orbits of the planets, not the stars. So when was it known to science that the stars are different distances away from the earth?
This answer was provided on History of Science and Math by user RommelTJ, and marked as correct. I have reproduced it here because of the unusual situation that occurred with this question. Normally we should not allow cross-posting.
As early as the sixth to fourth centuries B.C., Greek astronomers realized that there must be more than one star "canopy". For while the "fixed" stars moved around the Earth in a body, apparently without changing their relative positions, this was not true of the Sun, the Moon, and other objects (which were later discovered to be Mercury, Venus, Mars, Jupiter and Saturn). These objects were called planets (from a Greek word meaning "wanderer"), and it seemed obvious that they could not be attached to the vault of the stars.
In 240 B.C., Eratosthenes of Cyrene performed the first scientific measurement of any cosmic distance. By analyzing the shadow over Syene, Egypt, he estimated the size of the earth. However, the stars were still unmeasurable to them and they still believed they were stuck in a vault like diamonds.
Later astronomers, beginning with Hipparchus and ending with Claudius Ptolemy, worked out all the heavenly movements on the basis of a motionless earth at the center of the universe, with the moon 240,000 miles away and other objects an undetermined distance farther. This scheme held sway until 1543 when Nicholas Copernicus published his book, which returned to the view of Aristarchus.
So you could say that by 1543, scientists suspected the stars were different distances, but they couldn't prove it. The use of the parallax method was used to calculate cosmic distances, but the distances were so large that an accurate observation beyond the moon was difficult.
It wasn't until 1673 when Jean Dominique Cassini determined the parallax of Mars with the help of Jean Richer. Cassini then calculated that the distance between the sun and the earth was 86 million miles, which is fairly accurate as we now know.
By this point, Astronomers were CERTAIN that the stars were spread out in space and that some were closer than others, if only because some were brighter than others. However, even with better and better telescopes, they were unable to tell their distance except for the Sun. The Copernicus model was still true.
In 1838, German astronomer Friedrich Wilhelm Bessel used a "heliometer" to measure the parallax of 61 Cygni. He determined that the star had an arc of 0.31 seconds and thus had to be 64 trillion miles away. Two months later, British Astronomer Thomas Henderson measured the distance to the star Alpha Centauri.
Therefore, I would answer your question with: "1838, when Bessel made his breakthrough observation of the distance to 61 Cygni." I will dispute the current accepted answer that it was in 1718 with Haley's discovery because it answers that the stars had motion and not what the OP originally asked of "when was it known by science that the stars are different distances away from the earth?"
In 1718 Edmund Halley announced his discovery that the fixed stars actually have proper motion. (See Fixed Stars)
The idea of fixed celestial spheres had a long history, with gradual changes and reinterpretation.
The measurement of stellar parallax could be used to measure the Earth's orbit, but Halley (of Halley's Comet fame) showed that the stars move, and so that was the end of the "fixed celestial sphere" concept.
I argue that when Edmund Halley discovered that the stars move relative to each other was when it was clear that they must be at different distances. Even if two stars were at the same distance at some time, as they moved relative to each other they would soon be at different distances.
Fairly soon after Copernicus, once things like comets and the like were discovered the concept of crystal spheres was pretty much gone. By the time star clusters were found and galaxies discovered you had to figure that these were more distant than local stars. Newton's Law is another blow to any such idea.
The final proof would be when the stellar parallax was measured, and found to be different for different stars. The position of stars were measured 6 months apart and some had shifted relative to others. This would not happen if all were at the same distance.
The first successful measurements of stellar parallax were made by Friedrich Bessel in 1838 for the star 61 Cygni using a heliometer. Stellar parallax remains the standard for calibrating other measurement methods. Accurate calculations of distance based on stellar parallax require a measurement of the distance from the Earth to the Sun, now based on radar reflection off the surfaces of planets.
There was ancient Indian scholars who studied about different planets and stars. They have made different start constellation during their period. Also there is Jyothisha in India which was based on vedas which is also based on position of stars and planets. So answer to your question is from very old time you have not imagined, the vedic people knew where the stars were and their position changes according to time.
Ancient Indian astronomy is based upon sidereal calculation. The sidereal astronomy is based upon the stars and the sidereal period is the time that it takes the object to make one full orbit around the Sun, relative to the stars. It can be traced to the final centuries BC with the Vedanga Jyotisha attributed to Lagadha, one of the circum-Vedic texts, which describes rules for tracking the motions of the Sun and the Moon for the purposes of ritual. After astronomy was influenced by Hellenistic astronomy (adopting the zodiacal signs or rāśis). Identical numerical computations for lunar cycles have been found to be used in India and in early Babylonian texts. Aryabhata (476–550), in his magnum opus Aryabhatiya (499), propounded a computational system based on a planetary model in which the Earth was taken to be spinning on its axis and the periods of the planets were given with respect to the Sun. He accurately calculated many astronomical constants, such as the periods of the planets, times of the solar and lunar eclipses, and the instantaneous motion of the Moon.[page needed] Early followers of Aryabhata's model included Varahamihira, Brahmagupta, and Bhaskara II. Astronomy was advanced during the Sunga Empire and many star catalogues were produced during this time. The Sunga period is known as the "Golden age of astronomy in India". It saw the development of calculations for the motions and places of various planets, their rising and setting, conjunctions, and the calculation of eclipses. Bhāskara II (1114–1185) was the head of the astronomical observatory at Ujjain, continuing the mathematical tradition of Brahmagupta. He wrote the Siddhantasiromani which consists of two parts: Goladhyaya (sphere) and Grahaganita (mathematics of the planets). He also calculated the time taken for the Earth to orbit the sun to 9 decimal places. The Buddhist University of Nalanda at the time offered formal courses in astronomical studies. Other important astronomers from India include Madhava of Sangamagrama, Nilakantha Somayaji and Jyeshtadeva, who were members of the Kerala school of astronomy and mathematics from the 14th century to the 16th century. Nilakantha Somayaji, in his Aryabhatiyabhasya, a commentary on Aryabhata's Aryabhatiya, developed his own computational system for a partially heliocentric planetary model, in which Mercury, Venus, Mars, Jupiter and Saturn orbit the Sun, which in turn orbits the Earth, similar to the Tychonic system later proposed by Tycho Brahe in the late 16th century. Nilakantha's system, however, was mathematically more effient than the Tychonic system, due to correctly taking into account the equation of the centre and latitudinal motion of Mercury and Venus. Most astronomers of the Kerala school of astronomy and mathematics who followed him accepted his planetary model.
In Lucian of Samosata's "A true story" (2nd century AD) an outcome of a war between the king of the Moon Endymion and the emperor of the Sun Phaeton over the right to colonize Venus was decided by the reenforcements arrived to help Phaeton from Sirius. He also mentioned some troops from the Milky Way (or "from the Galaxy", "ἀπὸ τοῦ Γαλαξίου" as the story was written in Greek) who arrived too late.
Their neighbours were the Dog-acorns, Phaethon's contingent from Sirius. These were 5,000 in number, dog-faced men fighting on winged acorns. It was reported that Phaethon too was disappointed of the slingers whom he had summoned from the Milky Way, and of the Cloud-centaurs. These latter, however, arrived, most unfortunately for us, after the battle was decided (...)