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 unit 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 $\Re e^z$), but maybe polynomials have something more that allows a "mountain pass lemma" to apply ?