The simplest way would be to have an empire and a kingdom.
However ... exactly what is right with two kings is very much a contextual thing.
Your example ("the gargoyle king menaced the human king, saying...") may actually sound right within a given text. (Some text makes a deliberate choice of such explicit phrasing, usually as part of a rhythm in the text.)
Even if that is not the case, if your story treats the gargoyles as persons of equal merit to humans, then I would
not resort to assuming "king" meant human. If they had names I would use them, or if only the two kings are in the scene then "king" can be dropped from some instances of the text. Or perhaps the context would allow one or other attribution to be inferred: "In a gravelly voice he told the human king,..." vs "The gargoyle king menaced the flimsy fleshy human, saying..." etc. etc.