When was it discovered that the stars are not all lying on the same plane?

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.

SOURCE

The first successful measurements of stellar parallax were made by Friedrich Bessel in 1838 for the star 61 Cygni using a heliometer.[6] 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.[7]

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.

From wikipedia,

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.[25] 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.[26][27][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.[28][29]

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 (...)

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.

Update - I have copied RommelTJ's excellent answer from HSM.SE.

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.