The problem you are facing here (which is the correct order of words) has nothing to do with the fact you are using the "passato prossimo" to construct the sentence, but with the use of the interrogative pronoun "che" to begin the question. That is, you will have the same problem if trying to write a question beginning with "che" in present or future simple tense, for instance ("Che Paolo mangia?" or "Che mangia Paolo?" / "Che Paolo mangerà?" or "Che mangerà Paolo?").
These kind of questions are called "interrogative parziali" ("partial interrogatives") because you are making a question about some specific part of the sentence. In your example, assuming that Paolo is the subject of the sentence, you are asking about the direct object of the verb "mangiare". As this article of the Enciclopedia dell'Italiano Treccani explains, an "interrogativa parziale" is always introduced by which is called an "interrogative operator" that can be an interrogative pronoun (such as "che" or "chi"), an adverb (such as "come" or "quando") or an adjective (such as "quale"). In English, they are also called wh-questions because most of the interrogative operators begin with "wh-" (who, what, when, where, why, which).
This Treccani article also explains that, if you begin the interrogative sentence with the interrogative operator (as it happens in your example: you begin the sentence with the interrogative pronoun "che") and you want to express the subject of the sentence (and this subject is not the interrogative pronoun), you should usually write this subject at the end of the sentence. The Treccani article makes this example:
Quando è arrivato Marco?
This sentence begins with the interrogative operator "quando" and the subject "Marco" is written at the end. Similarly, the standard way of writting your question would be
Che ha mangiato Paolo?
with the subject "Paolo" at the end of the sentence.