**Step 1 (case $k=1$).** Fix $i \in \{1,\dots,n\}$ and set $a := r/2$. Since $u_{x_i}$ is harmonic,
\begin{align*}
|u_{x_i}(x_0)|
&= \left| \frac{1}{\mathcal{L}^n(B(x_0,a))} \int_{B(x_0,a)} u_{x_i}(y) \, d\mathcal{L}^n(y) \right|
&& \text{(mean-value for $u_{x_i}$)} \\
&= \left| \frac{1}{\mathcal{L}^n(B(x_0,a))} \int_{\partial B(x_0,a)} u(y) \, \nu_i(y) \, d\mathcal{H}^{n-1}(y) \right|
&& \text{(divergence theorem)} \\
&\le \frac{\mathcal{H}^{n-1}(\partial B(x_0,a))}{\mathcal{L}^n(B(x_0,a))} \, \|u\|_{L^\infty(\partial B(x_0,a))}
&& \text{($|\nu_i|\le 1$)} \\
&= \frac{n}{a} \, \|u\|_{L^\infty(\partial B(x_0,a))}
&& \text{($\frac{\mathcal{H}^{n-1}(\partial B(0,a))}{\mathcal{L}^n(B(0,a))}=\frac{n}{a}$)} \\
&= \frac{2n}{r} \, \|u\|_{L^\infty(\partial B(x_0,r/2))}.
\end{align*}
For any $x \in \partial B(x_0,r/2)$ we have $B\!\left(x,\tfrac{r}{2}\right) \subset B(x_0,r)$, hence by the $k=0$ case,
\begin{align*}
|u(x)|
&\le \frac{1}{\mathcal{L}^n(B(x,\tfrac{r}{2}))} \int_{B(x,\tfrac{r}{2})} |u(y)| \, d\mathcal{L}^n(y) \\
&\le \frac{1}{\frac{\pi^{n/2}}{\Gamma(1+\frac{n}{2})} (\tfrac{r}{2})^n} \, \|u\|_{L^1(B(x_0,r))}
= \frac{2^n C_0}{r^n} \, \|u\|_{L^1(B(x_0,r))}.
\end{align*}
Combining,
\begin{align*}
|\nabla u(x_0)|
\le \frac{2n}{r} \cdot \frac{2^n C_0}{r^n} \, \|u\|_{L^1(B(x_0,r))}
= \frac{C_1}{r^{\,n+1}} \, \|u\|_{L^1(B(x_0,r))},
\end{align*}
with $C_1 = 2^{\,n+1} n\, C_0$.