Paralyzed (or held) individuals are unable to move or take actions of any kind and are considered flat-footed. This is considered a mind-affecting effect (unless it originates from a death attack). A paralyzed non-player character with 4 or fewer hit dice is susceptible to a coup de grâce.
Petrification will override the effects of paralysis, including the susceptibility to a coup de grâce.