To hold a Medium creature motionless requires the harden air weave cast at 3rd level. It cannot be done with arms of air, which is described as using the air to LIFT a creature or object. You cannot, by definition, lift something DOWNWARD.
Harden air allows a Reflex save to avoid.
EDIT: Anyways, Padan Fain should be able to avoid being killed because he possesses the power of plot.