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 after 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'.
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 these two the former was meant to forebode the Last Battle and the latter to challenge Melkor and to act as sign of doom.