Building on David Speyer's answer, and as the problem (version 2) seems hard, I venture a (nonconclusive) argument for the case where $D^2f(x)$ has signature $+-$, on the plane. (I was meaning this as a comment, but it was too long...)
We probably can select smooth vector fields $e^+(x)$ and $e^-(x)$ in the positive and negative (orthogonal) directions (eigenvectors of $D^2f(x)$). This defines $X(s,t)\in\mathbb R^2$, $s,t\in\mathbb R$, with $\partial_s X=e^+(X)$ and $\partial_t X=e^-(X)$ (plus $X(0,0)=0$ for definiteness). Now $f(X(s,t))$ is strictly convex in $s$ and strictly concave in $t$, isn't it?
This doesn't prove $f$ has a saddle point (example $\mathrm{Re} (e^z)$), but maybe polynomials have something more that allows a "mountain pass lemma" to apply ?
EDIT That seemed plausible, but no: maybe there exists $X(s,t)$ such that $f(X(s,t))$ is convex in $s$ and concave in $t$, but it cannot satisfy $\partial_s X=e^+(X)$ and $\partial_t X=e^-(X)$, because the necessary integrability condition $(e^-\nabla) e^+=(e^+\nabla) e^-$ is (generically) incompatible with the orthogonality $e^+\cdot e^-=0$ (if I'm not mistaken again...)