A standard argument says that a continous function is $ C^{k,\alpha} $ at zero if there exists a polinomial of degree k such that $$ | (u - P)(x)| \le C | x|^{k+\alpha}. $$ This is the way for intance that Caffarelli does his interior estimates. Let $ k=2 $. We can see easilly that if $ u \in C^{2,\alpha} $ at zero. Then, the inequality above is satisfied with the constant $ C = \sup \{Du(x)\} $ and the polynomial $$ P(x) := u(0) + \langle Du(0), x \rangle + \dfrac{1}{2} x^t D^2u(0) x. $$
Here I want to obtain the reciprocal. that is, is there exists a polynomial satisfying the above inequality then, $ u \in C^{2,\alpha} $ at zero. Well, we can see that $$ u(x) := u(0) + \langle Du(0), x \rangle + \dfrac{1}{2} x^t D^2u(0) x + o(|x|^{2+ \alpha}). $$ Then, $ u \in C^2 $ at zero. Rest only to prove that its second derivatives are $ C^\alpha $ at zero. How to do this?
"Standard argument"? What you claim is false.
If true, then, taking $P=0$, it would follow that if $|u(x)|\le x^2$ then $u$ is better than $C^1$ at $0$. Define $$u(x)=\begin{cases}x^4,&(x\in\Bbb Q), \\0,&(x\in\Bbb R\setminus \Bbb Q).\end{cases}$$
Then $|u(x)|\le x^4$, but $u'$ has no chance of being continuous at the origin, since it's not even defined in any neighborhood of the origin.
(Possibly Caffarelli is very confused, or possibly he actually has some stronger hypothesis that you missed.)
Edit Now the OP says he forgot to say that $u$ is continuous. That doesn't help, the counterexample is just a little more intricate: Let $$u(x)=\begin{cases}x^4\sin(1/x^{10}),&(x\ne0), \\0,&(x=0).\end{cases}$$
Then $u$ is continuous, $|u(x)|\le x^4$, and $u$ is differentiable everywhere, but $u'$ is not continuous at the origin.
There simply is no such result - no rate of decay implies that $u'$ is continuous at the origin.