EPRock said:
A paralyzed or held character cannot move, speak, or take any physical action.
Does Fly require the character move? No. He displaces distance without moving.
Does it require he speak? No.
Does it require he take any physical action? No. He must merely concentrate on flying.
He is rooted to the spot, frozen and helpless. Not even friends can move his limbs.
You cannot "root" someone to air. Nice try though. Does a character with wings then become suspended in mid-air when held? No? Good.
I agree he's frozen and helpless. I'd allow someone to coup de grace a flying held creature (sorry, LokiDR.

)
Since flying doesn't require limb-moving, he's still fine.
He may take purely mental actions, such as casting a spell with no components.
Well bam, there you go. That line is GIVING him permission to keep flying, since Fly requires a "mental action". I don't care if the "mental action" you take is to mentally organize your grocery list, fly, or maintain a Dominate Person spell. The text of Hold Person allows you to keep doing it.
Well even if he is flying he is rooted in three directions no moving is possible.
Don't be an idiot, you know that's just plain silly.
I believe you're confusing two definitions for MOVE.
1) I walk forward 10 feet. I have MOVED (definition is displacing myself 10 feet)
2) I wave my arms around in the air. I have MOVED (definition is exercising my motor functions)
Now, MOST TIMES, if I cannot MOVE #2, I can also not MOVE #1. Afterall, if I have no motor functions, I cannot walk forward.
However, if I have no motor functions, and you put me on a conveyor belt, I AM moving per #1 (I am displacing distance) but I am not moving per #2 (I still have no motor functions).
You could argue that the CONVEYOR BELT is moving me, not ME. Okay, that's fine. Let's make the conveyor belt plugged into a microchip in my head. When I think about it, I can activate the conveyor belt. Now, deprive me of my motor functions and stick me on the conveyor belt. I think the belt to move... and I'm moving, and I'm also causing myself to move.
Hold Person prohibits MOVE #2. Not MOVE #1. I am still capable of displacing distance. Since Hold Person does not influence my concentration, I'm still free to think to activate the conveyor belt, and thus I'm also free to think to control my Fly spell.