I think flying could be greatly simplified, assuming you don’t want fly-able mazes.
You could pretty much always pathfind on a 2D grid, and if you have a target that is higher or lower in the air, then your pawn first moves to that Z by some simple process, and then pathfinds on the XY plane to the target. You should be able to handle combat in any open 3D space that way. I would have a few checks near the surface that might say, if distance is over X, then move up 1 Z and check again, if shorter, use second path, etc.
If you want dog fights to happen spontaneously in the air, weaving under arches and over rocks, things are going to get complicated. If you just want basic flight for the NPC’s, should be manageable, especially in open spaces.