The first stars were made by Varda in the very beginnings of Arda (Silmarillion Chap. 1) but she formed the constellations only later, during the age of the Trees when Mandos in a council of the Valar had foreboded the coming of the Elves and told that 'the Firstborn shall come in the darkness, and shall look first upon the stars. --- To Varda ever shall they call at need'.
After pondering at the words of Mandos, Varda decided to make new stars and also 'many other of the ancient stars she gathered together and set as signs in the heavens of Arda' (Silmarillion, Chap. 3).
Thus were formed the constellations of Wilwarin, Telumendil, Soronúmë, Anarríma, and as the most important ones, Menelmacar (or Telumehtar) and Valacirca. Of the two last ones the former was meant to forebode the Last Battle and the latter to challenge Melkor in the Northern skies and to act as the sign of doom of the Valar.
Evolution of the story
The constellations play their part already in the very early phase of the mythology of Arda in The Coming of the Elves and the Making of Kôr (LT1 113-139).
There the Elves are first brought to Valinor during the captivity of Melko and Varda, in order to commemorate the coming of the Eldar, makes new stars mingling the radiance of the Silver Tree that was stored in a basin with molten silver in Aulë's workshop. Of the constellations only the Seven Stars (The Great Bear) is mentioned, and its' birth is ascribed either to Aulë or (in a separate note) to Varda (See the article on Valacirca and LT1, 114, 133). Later, in The Tale of the Sun and the Moon there is a reference to Telimektar (Orion) and in the end of the Tale the Moon is told to beg the 'starry mariners flee before him and the constellate lamps go out' (LT1, 195).
The development of Telimektar (q. v.) from a Vala, son of Tulkas, to the constellation of Orion follows its own path, separate from the the story of the making of the constellations until it is abandoned. Only in the latest versions of the Silmarillion Telimektar-Orion is taken to the company of other constellations with another name and character, Menelmacar the Swordsman. So, let us continue the main path:
In the next phase, "The Sketch of the Mythology" (SM 11-75), written c. 1926-30, the making of the stars is already contemporary with the awakening of the Elves (SM 12), but the constellations are not mentioned. Only in The Quenta (SM 76-218), written in 1930, Varda makes the stars before the coming of the Eldar and also creates The Great Bear (SM 84), also mentioned in The Earliest Annals of Valinor (SM 262-293) at the Valian year 2000 (later changed to 1900) (SM 264, 272).
In another pre-LoTR composition, The Later Annals of Valinor (LR 109-123), written between 1930 and the end of 1937 (cf. LR 107) in the entry of Valian year 1900 Varda is told to have begun "the fashioning of the stars" (LR 111) and in V. Y. 1950 she made the Sickle of the Gods or the Great Bear. No other constellations are mentioned.
The Sickle only gets company in The Annals of Aman (MR 47-138) with which Tolkien worked after finishing The Lord of the Rings (cf. MR 47). There the stars are told to have been made in V. Y. 1000-1050 with Menelmakar, Orion (now set apart from the story of Telimektar), and only after that, in V. Y. 1050, Valakirka, the Sickle.
Finally, in The Later Quenta Silmarillion I (MR 141-199), also written after the completion of The Lord of the Rings, in the early 1950's (cf. MR 141), the list of the constellations is complete (MR 159-160) and the Elves awake just "when first Menelmakar strode up the sky" (MR 160). The printed text in the Silmarillion (Chap. 3) does not essentially deviate from this but in wording and in leaving out some details.
To conclude, the presence of the constellations in the heavens of Arda was from the very beginning tied with the evolution of the story of the second making of the stars by Varda connected to the awakening of the Elves. The Sickle of the Valar or the Great Bear was the first of the constellations, and as the story evolved, other constellations were added, but of these only Telumehtar-Menelmacar had some deeper character and a mythology which evolved separately from the story of the other constellations.
This poem by Tolkien (LT1, 33-43) was first written in 1915 and revised in further instances. It was dedicated to Warwick, town where at that time lived Tolkien's bride Edith Bratt. Warwick was the model of Kortirion, city of the Elves in the Lonely Isle.
The poem belongs to the period when the mythology of the Silmarillion was in its cradle, so further analysis would be superfluous, but let us mention that in this poem by 23-years-old Tolkien two constellations are mentioned: the Silver Bear (LT1 33, 35), later replaced by he Silver Wain (LT1 39, 43) and the Seven Stars (LT1, 38, 42), which here probably stands for the Pleiades (cf. C. Tolkien in LT1, 291).
LR = The Lost Road and other Writings (The History of Middle-earth, vol. 5)
LT1 = The Book of Lost Tales 1 (The History of Middle-earth, vol. 1)
MR = Morgoth's Ring (The History of Middle-earth, vol. 10)
SM = The Shaping of Middle-earth (The History of Middle-earth, vol. 4)