Indeed it is true that all proofs of the fundamental theorem of algebra need some piece of analysis. Even the most algebraic proof of FTA (Euler, Gauß II) relies on the fact that all odd-degree real polynomials have at least one real root.
First consider the case of relatively large positive $x$. Assuming $x\ge 1$ as provisional lower bound, then $1\le x^k\le x^{2n}$ for $0\le k\le 2n$ and the value of the polynomial is bounded below by
$$
P(x)\ge x^{2n+1}-\sum_{k=0}^{2n}|a_k|x^k\ge x^{2n+1}-x^{2n}\sum_{k=0}^{2n}|a_k|
=x^{2n}\left(x-\sum_{k=0}^{2n}|a_k|\right)
$$
We can now try to push the last expression on the right into positive territory by increasing the lower bound for $x$. At the Lagrange root bound $$
R=\max\left(1,\sum_{k=0}^{2n}|a_k|\right),
$$
the right side for $x\ge R$ gives a non-negative bound. Increasing the lower bound to $x\ge 2R$ will result in
$$
x≥2R \implies P(x)\ge (2R)^{2n}\cdot R\ge 2^{2n}>0.
$$
The same reasoning can be applied to $-P(-x)=x^{2n+1}-a_{2n}x^{2n}+a_{2n-1}x^{2n-1}\mp...-a_0$, so that
$$x≤-2R \implies P(x)≤-(2R)^{2n}\cdot R≤-2^{2n}<0.$$
In total one obtains
$$
P(-2R)≤-(2R)^{2n}\cdot R ≤ -2^{2n}<0<2^{2n}≤(2R)^{2n}\cdot R≤P(2R)
$$
which allows to apply the intermediate value theorem for $P$ concluding for a real root of $P$ inside $(-2R, 2R)$, but really already inside $(-R,R)$.