Proof of fundamental theorem of algebra in Baby Rudin
No part of the proof of this theorem relies on any complex analysis other than what Rudin has already developed in this chapter. Rudin has already introduced the complex numbers as well as properties of the exponential function, the latter of which is discussed in the preceding section in the same chapter.
The usual complex-analytic proof breaks down into two steps.
Step 1. If $p(z)$ has no zeros then $\dfrac{1}{p(z)}$ is bounded.
The proof of this is essentially the same as what has already been done. For $|z| > R_0$ we have $|p(z)| > \mu + 1$ and hence $\frac{1}{|p(z)|} < \frac{1}{\mu + 1}.$ For $|z| \le R_0$ we have a continuous function on a compact set so that's going to be bounded.
Nothing in this step is material that is unique to complex analysis (i.e. that can't be found in real analysis).
Step 2. Every bounded, complex differentiable function is constant.
This is something that doesn't happen on the reals. For instance $\frac{1}{1 + x^2}$ is bounded and differentiable everywhere. In the complex plane, this function blows up near $\pm i$. For $\sin(x)$ one has
$$ \sin(ix) = \frac{e^{i(ix)} - e^{-i(ix)}}{2i} = \frac{e^{-x} - e^{x}}{2i} $$
which blows up as $x \to \infty$.
Step 2 is called Liouville's Theorem. The proof uses Cauchy's Integral Formula which says that if $f$ is complex differentiable everywhere then the $n$-th derivative at $z_0$, $f^{(n)}(z_0)$ can be computed by integrating along a closed path around $z_0$ counterclockwise (e.g. along a circle) by
$$ f^{(n)}(z_0) = \frac{n!}{2\pi i} \oint_\gamma \frac{f(z)}{(z - z_0)^{n + 1}} dz.$$
To prove Liouville's theorem we let $\gamma = \gamma_R$ be the circle centred at $z_0$ of radius $R$. Then on $\gamma_R$, $|z - z_0| = R$. Hence if $|f(z)| \le M$ is bounded
\begin{align} |f^{(n)}(z_0)| &= \left\lvert \frac{n!}{2\pi i} \oint_{\gamma_R} \frac{f(z)}{(z - z_0)^{n + 1}} dz \right\rvert \\ &\le \frac{n!}{2\pi} \oint_{\gamma_R} \left\lvert \frac{f(z)}{(z - z_0)^{n + 1}} \right\rvert dz \\ &= \frac{n!}{2\pi} \oint_{\gamma_R} \frac{M}{R^{n + 1}} dz \\ &= \frac{n!}{2 \pi} \frac{M}{R^{n + 1}} \operatorname{length}(\gamma_R) \\ &= n!\frac{M}{R^n} \end{align}
since $\operatorname{length}(\gamma_R) = 2\pi R$ (the circumference of a circle with radius $R$). Now taking $R \to \infty$ it follows that $f^{(n)}(z_0) = 0$ for all $n \ge 1$. Hence $f$ is constant.
For comparison the proof in Rudin's book is more direct. If one were to define a line between complex analysis and real analysis, Cauchy's Integral Formula would be a major part of the distinction. Since Rudin does not use Cauchy's Integral Formula, I think it is safe to say that the proof does not involve complex analysis in any way.