It sounds like you've settled on rēgēs for "kings", which is a perfectly good word for that purpose. And to the Romans it would most certainly imply that they were supremely confident, as people at the time did not like kings—Caesar and the later emperors specifically avoided the term.
For "of the stars" you have several options, each with their own benefits and drawbacks.
Sīderum (from sīdus, sīderis): a poetic term, which can mean "stars", "constellations", "the night sky", or even "the heavens". It's a rather grandiose (and slightly pretentious) word to use in your title…sort of like using a Latin title in English!
Astrōrum or Asterum (from astrum, -ī or astēr, asteris): borrowed from Greek ἄστρον and ἀστήρ, these terms eventually started to replace the native Latin words. Astrum was considerably more common than astēr, though both would be understood. In Classical times these words were still a bit exotic and found "poet[ically] or in more elevated prose", as Lewis and Short put it, though they were still less poetic than sīdus.
ETA: astrum would be a slightly more poetic form than astrōrum, with the same meaning.
Stellārum (from stella, -ae): stella is the most neutral, standard word for a star or other heavenly body. Calling a single star a sīdus, for example, would be somewhat akin to referring to the sky as "the great vault of the heavens" in normal conversation. Planets were stellae errantes, comets were stellae comantes, and meteors were stellae lābentes (or sometimes just stellae).
ETA: stellum would be a slightly more poetic form than stellārum, with the same meaning.
Caelī or Coelī (from caelum, -ī): "heaven", or literally "the sky". This is the most arrogant option out of all of these, as "the King of Heaven" or "the King of the Sky" was a title of Jupiter (and later of the Christian God). But if your characters have reached that point, they might find such a title perfect.