Assuming Choice, every field has an algebraic extension containing roots of all nonconstant base polynomials

By [L1] and the maximal-ideal theorem [L2], whose choice step is Zorn's lemma [L5], choose a maximal ideal $M$ of $A$ containing $I$.

Put $L=A\mathrm{/}M$. By [L3] this is a field. The composite $F\to A\to L$ is injective, since a nonzero scalar in $M$ would be a unit and force $1\in M$, so it identifies $F$ with a subfield of $L$.

For each $f\in \mathcal{S}$, the residue $\overline{x_f}\in L$ satisfies $f(\overline{x_f})=0$ because $f(x_f)\in I\subseteq M$. Multiplying an arbitrary nonconstant polynomial by the inverse of its leading coefficient makes it monic without changing its roots, so every nonconstant polynomial over $F$ has a root in $L$.

Every element of $L$ is represented by a polynomial involving finitely many variables $x_{f_1},\dots ,x_{f_r}$, hence lies in $F(\overline{x_{f_1}},\dots ,\overline{x_{f_r}})$. Each residue is algebraic over $F$, so [L4] makes this subextension finite and [L6] makes it algebraic. Thus $L\mathrm{/}F$ is algebraic.

The field $L$ constructed above is the required algebraic root extension, and the only choice principle used is the maximal-ideal application in step 1.1.