Existence of a particular kind of polygonal subdivisions of surfaces Let $\Sigma$ be a closed, compact, connected, oriented smooth $2$-manifold (in other words, a sphere or a torus with $g$ handles). We may draw smooth arcs on the surface in such a way that they cut it up into polygons. Call this configuration a polygonal subdivision of $\Sigma$. We say that such a subdivision is $n$-regular if it consists only of $n$-gons and is such that exactly $n$ polygonal faces meet at every vertex of the subdivision.
For instance, the tetrahedron is a $3$-regular polygonal subdivision of the sphere. As a second example, the following figures induce $4$-regular subdivisions of the torus after identifying opposing sides of the square:
$4$-regular subdivisions of the torus" />
One may obviously produce an infinite family of this kind by refining the mesh.

Q: Is it possible to construct $n$-regular subdivisions of surfaces of arbitrarily high genus?

By an Euler characteristic argument we have some fairly obvious conditions over the possible genus of a surface admitting an $n$-regular subdivision. Indeed, if $v,e,f$ denote the number of vertices, edges and faces respectively, then $v=f$ and $nf/2=e$, so the Euler formula $v-e+f=2-2g$ implies:
$$4g-4=(n-4)f$$
This imposes some restrictions that an eventual example must satisfy. Are there finer invariants that present obstructions to this kind of construction? If there are no obstructions, is there an easy way to construct them?
 A: There are no further obstructions beyond the Euler obstruction you point out and there is a simple construction of examples in each class.
You have already given constructions for all possibilities for $g<2$ except $g=0$ and $n=2$, which is easy.
Douglas Zare, in a deleted answer, described how constructing the surface of genus $2$ by identifying sides of an octagon in pairs provides an $8$-regular subdivision of the surface of genus $2$ (with $f=1$). More generally, a similar standard construction works for all $g\ge 2$, giving a $4g$-regular subdivision of the surface of genus $g$ (with $f=1$). Below, I will outline two other similar constructions, one for $g=2k$ and $n=2k+3$ with $f=4$ and the other for $g=2k$ and $n=4k+2$ with $f=2$. This gives a base construction for every $n>4$.
Suppose we have these base constructions for all $n>4$. Let $(g,n)$ be an arbitrary pair (with implicit $f$) satisfying your Euler equation with $g>1$. Then $n>4$ and by Euler characteristic the surface of genus $g$ covers the surface with the base construction (this can be seen in three cases which I will omit for now but can add if desired). Then as Douglas pointed out in the deleted answer, the base construction can be lifted to the genus $g$ surface.
Thus the problem is reduced to giving the other two base constructions. The following two constructions are probably known classically but were described to me by Seonhwa Kim.
Consider first the case with even genus $g=2k$ and $n=4k+2$. Cut the surface of genus $g$ into two surfaces with boundary, each of genus $k$ with one boundary component. Using a variation of Douglas' construction with two extra edges for the boundary component, a surface of genus $k$ with one boundary component can be constructed from a $4k+2$-gon identifying $4k$ of the faces in pairs. The resulting surface has two vertices each of valence $2k+2$. Gluing the two of these together along their boundary gives a $4k+2$-regular decomposition of the genus $g$ surface.
To get the case with even genus $g=2k$ and $n=2k+3$, take the $4k+2$-gon described in the previous paragraph and cut it with an edge between the midpoints of the non-identified edges making up the boundary component. This yields a decomposition of the surface of genus $g$ with one boundary component into two $2k+3$-gons with  four vertices, two of valence $3$ and two of valence $2k+2$. Gluing two such decompositions together with a quarter-twist so that the vertices of valence $3$ on one side are paired with the vertices of valence $2k+2$ on the other side yields a $2k+3$-regular decomposition of the genus $g$ surface.
