Was it the Rig Vedic king Sudas? He is said to have fought in the battle of ten kings.
Who was the earliest Sudra king?
The first Shudra king existed in Kali Yuga. Shudras being kings is a symptom of Kali Yuga.
From the Vishnu Purana on the symptoms of Kali Yuga:
In the Kali age every one who has cars and elephants and steeds will be a Rájá.
From the Bhagavata Purana on the degraded dynasties of Kali Yuga:
12.1.37 - The land along the Sindhu River, as well as the districts of Candrabhāgā, Kauntī and Kāśmīra, will be ruled by śūdras, fallen brāhmaṇas and Mlecchas. Having given up the path of Vedic civilization, they will have lost all spiritual strength.