He had to have his appendix out.
out is short for taken out, so its part-of-speech is verb, not adverb.
had to is an auxiliary modal verb expressing deontic necessity.
have is not an auxiliary verb as it often is (e.g. in I have eaten, have is an auxiliary verb forming the past perfect). In your sentence, have is the main verb and has this dictionary meaning:
have
2. experience or suffer the specified action happening or being done to (something).
"she had her bag stolen"
(Oxford Languages)
The action that is being done to his appendix is... taken out, shortened to out in your sentence.
take out is a phrasal verb. In take out, out is a particle because it can go either after take's direct object (take it out) or in-between the verb and its direct object (take out the gun). Being able to put a noun in-between a verb and a preposition while the verb phrase retains the same meaning proves that you are dealing with a phrasal verb, rather than a verb with a prepositional phrase argument (e.g. stand on the truck but not *stand the truck on).