All perfect praise be to Allaah, The Lord of the Worlds. I testify that there is none worthy of worship except Allaah and that Muhammad is His slave and Messenger.
Mentioning the details of the religion of these kings and others is not the nature of the fataawa at Islamweb, but you can find such details in books of biographies, history and interpretations of ahaadeeth. Nonetheless, we will mention the religion of those whom you mentioned in the question in brief.
As for Ukaydir Domah, who was the King of Domah, then Ibn Hajar said in al-Fath, “Domah is a country between Hijaaz and the Levant, and it is Domat Al-Jandal, a town near Tabook; it has palm trees and plantations, and a fort, at ten marhalahs (one marhalah equals 8 farsakh, each farsakh equals 3 miles) from Madeenah and at eight marhalahs from Damascus. Ukaydir was its king, whose name is Ukaydir ibn Abdul Malik ibn Abd Al-Jinn ibn A'baa' ibn Al-Haarith ibn Mu'aawiyah; he is traced back to Kindah, and he was a Christian.”
The Muqawqis, the King of the Copts, was a Christian.
Kisra, the king of the Persians, was a Maji.
The Emperor Heraclius was a Christian.
The king of Aylah was a Christian.
Farwah ibn Nufaathah was a king of part of the Levant in the pre-Islamic era of ignorance; he was a Christian, then he became a Muslim.
As regards 'Iyaadh ibn Himaar, he was a pagan, and he was an old friend of the Prophet then he became a Muslim.
As for why the Prophet did not accept his gift at the beginning, then Al-Khattaabi said in Ma’aalim as-Sunan:
“There are two reasons for him refusing his gifts: one reason is to make him angry by refusing his gift and that this would be an admonition for him; this would lead him to embrace Islam. The second reason is that the gift affects the heart, and the hadeeth reads, 'Exchange gifts, you would love each other.' But it is not permissible for him that his heart would be softened towards a polytheist, so he refused the gift in order to eradicate the reason of being sympathetic towards him. It has been proven that the Prophet accepted the gift of An-Najaashi (Negus), and there is no difference of opinion about this, as he said, 'I was forbidden from taking gifts from the polytheists,' as An-Najaashi was a man from the People of the Book, and he was not a polytheist. It is known that we are permitted to eat the food of the People of the Book and marry their women and that this is contrary to the ruling on the (food and women of the) polytheists.”
It is clear that the word mushrik (polytheist) in the hadeeth of Iyaadh was interpreted by Al-Khattaabi to refer to the polytheists other than the People of the Book, but there is a difference of opinion on the issue. Ibn Hajar held the view that, “The opinion of those who interpreted refusing the gift to apply to the idolaters only apart from the People of the Book is invalid.”
Allaah knows best.