A counterexample is given by
$$
f(x,y)=(x^4-y^3)^2+y .
$$
Clearly, $f(R, R^{4/3})=R^{4/3}\ll R^2 = \left( \min \{ R, R^{4/3} \} \right)^2$, so $f$ doesn't satisfy your condition.
However, $f$ is coercive: If $y\le 0$, then $f(x,y)\ge x^8+y^6 +y$ and now either $|y|$ is not large and there are no problems or if $|y|\gg 1$, then $y^6+y\ge (1/2)y^6$, say.
If $y\ge 0$, then $f(x,y)\ge \max\{ (x^4-y^3)^2, y\} \to\infty$ as $|(x,y)|\to\infty$, $y\ge 0$.
The answer is still (surprisingly to me!) yes. As you've already established, there must exist $L = \lim \frac{||x_n||}{n}$ (I will never write a vector symbol over the variable). If $L = 0$ then there is nothing to prove. Otherwise, assume for simplicity that $L = 1$ by scaling. Let $x_n = c_n v_n$, $||v_n|| = 1$, $\lim \frac{c_n}{n} = 1$.
First, obeservation: for all $s > 1$ and all $\delta > 0$ there exists $N$ such that for all $N \le n \le m \le sn$ we have $\langle v_n, v_m \rangle \ge 1 - \delta$ (that is, the angle between $v_n$ and $v_m$ is small). Indeed, just go far enough in the sequence so $\frac{c_n}{n}$ is very close to $1$, then if the angle is big enough, by the law of cosines (and comparable sizes of $c_n$ and $c_m$ due to the $s$ restriction) we will get that $c_{n+m} < (n+m)$ -- a contradiction.
Now, our goal is to prove that the sequence of $v_n$ is Cauchy, then its limit will be our limit as well (in particular, I believe that the compactness of the unit sphere is not needed and so this proof will work even in the Hilbert space).
So, assume that we picked some very large number $N$ and nevertheless for some $N < n < m$ we have $\langle v_n, v_m \rangle < 1 - \delta_0$ (that is, the angle is not small). Importantly, $\delta_0 > 0$ is fixed but $N$ we can get as big as we like later. Then, from the above observation we know that $m$ is much bigger than $n$. Direct computation with law of cosines (and the fact that $c_m$ is much bigger than $c_n$) then shows that $||x_n + x_m|| \le c_m + \gamma c_n$ for some $\gamma < 1$ (this $\gamma$ is related to the $\delta_0$ above, but making it explicit is not pleasant). So, $c_{m+n} \le c_m + \gamma c_n$.
Here is the idea: $n+m$ and $m$ are still very close since $n$ is much smaller than $m$. So, we can invoke the above observation telling us that the angle between $v_{m+n}$ and $v_m$ is small. But this means that the angle between $v_{m+n}$ and $v_n$ is not small. So, we can repeat this procedure again and get that $c_{m+2n} \le c_m + 2\gamma c_n$.
How many times can we repeat this? By picking $N$ big enough, at least until $m + kn \le sm$. Picking the biggest such $k$ we get $c_{m+kn} \le c_m + k\gamma c_n$. Recall that $c_{m+kn} \ge m + kn$. So, combining this we get
$$m + kn \le c_m + k\gamma c_n.$$
Finally, if $N$ is big enough $c_n < (1+\varepsilon)n$, $c_m < (1+\varepsilon)m$. Plugging this in we get
$$m+kn \le (1+\varepsilon)(m + k\gamma n).$$
Recall that $kn = m(s-1)$ (the right hand side might not be divisible by $n$, but adjusting it is not a big deal since once again $n$ is much smaller than $m$). So,
$$sm \le (1+\varepsilon)(m + \gamma m(s-1)).$$
Dividing by $m$, we get $s \le (1+\varepsilon)(1 + \gamma (s-1))$, which is equivalent to (if $(1+\varepsilon)\gamma < 1$, which we can always achieve taking $\varepsilon$ small enough)
$$s < \frac{(1+\varepsilon)(1-\gamma)}{1-(1+\varepsilon)\gamma}.$$
But the observation works for any $s > 1$ -- contradiction! (on further thought, by picking $\varepsilon$ arbitrarily small it is enough to use the observation for any fixed $s_0 > 1$, but since this version is clearly equivalent to the version with arbitrary $s > 1$ I don't think it is any easier, but also makes the ideas less obvious).
Best Answer
The assumption "$\lim_{R\to\infty}m_f(R)\to\infty$" already includes $\bf P$ as remarked in comments, and it is the same as $\lim_{\|x\|\to\infty} f(x)=+\infty$, that is: $f$ is a coercive polynomial. You are asking whether a coercive polynomial in $n$ variables needs to go to infinity at least quadratically: the answer is no: the order of coercivity of a coercive polynomial may be an arbitrarily small positive number.
Check e.g. this article, How fast do coercive polynomials grow? (section 4 for examples). In particular (proposition 19), even in two variables, for any $k\in\mathbb N_+$, $$f(x,y)=x^2+(y-x^{2k})^2$$ is coercive and has order of coercivity $1/k$, that is $f(z)/{\|z\|^\theta}\to\infty$ as $\|z\|\to+\infty$, for $\theta<1/k$, but for no $\theta>1/k$ (just because along the curve $y=x^{2k}$ one has $f(x,y)=x^2=y^{1/k}$, so that $f(z)/{\|z\|^{1/k}}=O(1)$)