Muhammad was the caliph of whole of Arabia. He had absolute control on everything like a king. So he was the king of Arabia. This a matter of pride for Muslims,nothing to be ashamed.
Mr Pagan there is no concept of hierarchy viz a viz ruling a state in Islam.
There are some traits which are must for choosing a ruler according to Islam.
Prophet (PBUH) was not a king. The areas under Muslims were distributed into administrative units and ruled by different administrators who were accountable to the court of justice, Qazis (judges). All the administrative things were decided by these admins.
Even the Prophet Muhammad (SAW) was accountable to the judges
You need to understand the concept of caliph to understand the administrative set up in the era of Prophet (SAW) .
In a Kingdom or kingship, the rule is automatically transferred to the kins whereas Caliphat, Khilafat its not the methods.
The next caliph is selected through mutual understanding keeping in view the characteristics of the person. (That was the original method) and what we see today in Saudi Arabia or even so-called democracy that is just a family business.
Anyway for implementing Islamic system of governance, we first needs a welfare state and no Muslim country currently is a welfare state.