Some city names I know of the top of my head:
Baraqesh, is Ytl, I am not sure how they place vowels in South Arabian so I'm guessing it was Yathal or Yathel, etc... If it is more closely related to Arabic then it would be Yathal if not then probably Yathel or Yathil.
Qarnaawu , or Qrnw. The vowels in it I am not sure of, perhaps Qarnewu as I do not know if the hard ā is as popular in Sabaen/Minaen as it is in Arabic, especially since it is not as close as Hebrew.
Ma'in, and without vowels M'n. The alif within it is a definite, however the 'in, could have been an 'een.
Ma'rib, M'rb, this is how it is said in Arabic, not sure exactly how it would be said by the Saba'iyyun.
Sayhaad, modern al-Ramlat Saba'tayn, was the old word for the desert of Yemen corresponding to the ancient south Arabian kingdoms. It likely was either the actual word used by the Yemeni's themselves or an Arabic play on the original word.
Timna or Teman, Tmn, the capital of the Qatabani kingdoms.
Hadramuut, in MSA known as Hadramawt.
Unfortunately most of the works on South Arabia are tainted by contemporary Arab sources who emphasized the history of Hijaz and Nejd as its what most pertained to Muhammad.
However I would suggest a book by Jawad Ali, "The history of Arab states before Islam", it is available in Arabic, and maybe Farsi, I am not for sure.
Then take your pick of the Arabic scholars of the past to use for King names, they give great genealogy lines for these kingdoms despite knowing relatively little about the kingdoms of those times in an actual scholarly fashion and not a folk form.
All correct. The most common transliterations I have seen are "Yathill" and "Qarnaw" respectively.