Gauss's first proof contained an enormous gap, since he presumed facts equivalent to the Jordan curve theorem to be true. Jordan curve theorem was proven a century later.

There is a modification on Gauss's first proof that uses only basic real analysis concepts (continuity and least upper bound principle for real numbers) on the real and complex parts of a complex polynomial (which are bivariate polynomials in either $(r,\theta)$ or $(x,y)$: On Gauss's first proof of the fundamental theorem of algebra

Sorry for the self promotion, I am an author in the proof.