I want to refrain from using an adjectival phrase because I would prefer to avoid any confusion ('Governorate-generals were headed by governors-general appointed by monarchs whose job was to keep an eye on governors under their supervision,' it's not clear whether it was monarchs' or governors-general's job).
"Monarch-appointed" is perfectly fine as a compound adjective. However, "prime minister" is not a compound adjective and should be written without the hyphen.
Another possibility to avoid the ambiguity you described is:
Governorate-generals were headed by governors-general appointed by monarchs, and their job was to keep an eye on governors under their supervision.