As I mentioned in the comments, it is a consequence of the MRDP theorem that the computably enumerable sets of natural numbers are precisely the projections of the natural-number zero sets of the multi-variable polynomials over the integers. That is, a set $A\subset\mathbb{N}$ is computably enumerable just in case there is a polynomial $p(x,\vec y)$ over the integers such that $n\in A$ just in case $\exists \vec m\in\mathbb{N}$ such that $p(n,\vec m)=0$. (One can equivalently work over $\mathbb{Z}$ rather than $\mathbb{N}$.)
Another widely used characterization of the c.e. sets is as the $\Sigma_1$-definable sets. These are the same as the projections (onto the first coordinate) of the primitive recursive or even the regular subsets of pairs of natural numbers. Thus, if you are willing to use your algebraic characterizations of regular subsets of the plane, then all you have to do is project onto the first coordinate to get the c.e. sets. This projection operation amounts to an unbounded existential quantifier: $a\in A$ just in case $\exists b\ (a,b)\in B$, where $B$ is a very simple subset of the plane.
The unbounded-search nature of projection will be absolutely required for any characterization of the c.e. sets, because there can be no computable bound on the length of time required to verify whether a given element is in a given c.e. set, for otherwise every c.e. set would be decidable, which would violate the unsolvability of the halting problem.
