Why no higher-genus polyhedra that are nearly regular? It seems to be a fact that there are only five bounded connected non-selfintersecting polyhedra with identical regular-polygon faces and congruent vertices (i.e., you can pick a neighborhood of every vertex so that all the neighborhoods are congruent, this is sometimes called "locally vertex-transitive"), namely the platonic solids.
(Drop any one word in the above and you get more: unbounded allows an infinite linear chain of octahedra glued face to face; disconnected allows the union of two disjoint Platonic solids; self-intersecting allows two of the Kepler-Poinsot solids; non-identical allows Archimedean solids; irregular faces allows e.g. the noble disphenoid, and of course dropping congruent vertices allows a myriad of possibilities.) Note I have not included convex among the hypotheses.
However, I am hard-pressed to put together a proof of this. If you add the hypothesis that the polyhedron is genus 0, then Euler's formula shows you there must be an overall angle defect, so the same angle defect at each vertex since the vertices are congruent, and now you can do the usual three times the vertex angle must be less than a full circle, etc. (Even in the case of genus 1, Euler's formula just tells you that the angle sum must be 0 at each vertex, and then there are infinite solutions for both six triangles and four squares at each vertex -- basically infinitely long prisms, which are projectively speaking tori -- so you will really need to use the boundedness...)
Nevertheless, the genus-zero hypothesis doesn't seem to be necessary; there seem to be no higher-genus connected bounded non-selfintersecting polyhedra with identical regular-polygon faces and congruent vertices.  Can anyone outline or point me to a proof of this fact? 
 A: Here is one reference where the author does not assume genus 0: He gives careful definitions and proofs:
Cromwell, Peter R., Polyhedra., Cambridge: Cambridge University Press. xiii, 451 p. (1999). ZBL0926.52014.
In Chapter 10 he gives a complete classification of embedded polyhedral surfaces $S$ in $E^3$ which are closed (compact, without boundary) and connected as topological surfaces and satisfy:


*

*Each face is a regular convex polygon and all faces are congruent. 

*Links of any two vertices are congruent. (In other words, for any two vertices $v, w$ of $S$ there are neighborhoods of these vertices in $S$ which are congruent in $E^3$.)  

*All dihedral angles are equal. (Not sure if this is an independent condition.) 
All regular polyhedra listed by Cromwell have genus zero.
Edit. I do not have an answer to your precise question: The assumption that Cromwell makes about equality of all dihedral angles forces $S$ to be locally convex, hence, convex. However, with a bit stronger assumption than the one you make, your question does have positive answer: 
Theorem. Suppose that $S$ is a uniform 
(embedded) connected closed polyhedral surface in $E^3$, i.e. such that:
a. All faces of $S$ are regular polygons. 
b. The symmetry group of $S$ acts transitively on the set of vertices of $S$. 
Then:


*

*$S$ is simply-connected. 

*If, in addition, all faces of $S$ are congruent to each other, then $S$ is the boundary of one of the Platonic solids.  
Remark. A symmetry of $S$ is an isometry of $E^3$ which preserves $S$. 
A classification of all uniform polyhedral surfaces (with references) can be found in this Wikipedia article (which also allows for non-embedded surfaces). The conclusion of the theorem stated above comes from examination of the list. The references for completeness of the list are:


*

*S. P. Sopov,   "A proof of the completeness on the list of elementary homogeneous polyhedra", Ukrainskiĭ Geometricheskiĭ Sbornik (8) (1970) 139–156.

*J. Skilling, "The complete set of uniform polyhedra", Philosophical Transactions of the Royal Society of London, 278 (1975)  111–135
However, in your question instead of vertex-transitivity of the group of symmetries you only assume local transitivity:
For any two vertices $v, w$ of $S$ there exist neighborhoods $U_v, U_w$ of $v, w$ in $S$ and an isometry $g\in Isom(E^3)$ which carries $U_v$ to $U_w$. 
This is a weaker assumption than vertex-transitivity and I am not sure it suffices for the desired conclusion (even assuming, in addition, that $S$ has genus 0). 
Definition. A (closed, connected, embedded) polyhedral surface in $E^3$ is called pseudo-uniform if its faces are regular polygons and $S$ is locally vertex-transitive but not vertex-transitive. 
They are discussed in this Wikipedia article: 

There are two known pseudo-uniform polyhedra: the pseudorhombicuboctahedron and the pseudo-great rhombicuboctahedron. It is not known if there are any others; Branko Grünbaum conjectured that there are not, but thought that a proof would be "probably quite complicated".

The first of these two surfaces is convex but its faces are squares and triangles, hence, they are not all congruent. The second surface is not embedded (and, again, has non-congruent faces). As far as I can tell, Grunbaum's conjecture is still open. If true, it will imply the positive answer to your question. However, clearly, his conjecture is harder since he does not assume congruence of all faces. 
In 
Gillispie, Steven B.; Grünbaum, Branko, The ({4,5}) isogonal sponges on the cubic lattice, Electron. J. Comb. 16, No. 1, Research Paper R22, 28 p. (2009). ZBL1160.52011.
the authors define Platonic polyhedra as those which are locally vertex-transitive and have regular and congruent faces. They make no comments about the classification about such polyhedra (apart from the classical case of convex polyhedra). Using their terminology, your question can be formulated as:

Suppose that $S$ is a closed connected polyhedral surface in $E^3$ which is a Platonic polyhedron. Is it true that $S$ is convex?

Considering surfaces of genus $1$, it is easy to see that the only examples can occur when faces are triangles and all vertices are 6-valent; it is a polyhedron of type $P(3,6)$ in the standard terminology. For each vertex, up to congruence, there is a 3-dimensional family of deformations in $E^3$ of the star of the vertex...
A: The problem is of geometric nature.
There are indeed combinatorially feasible regular "figures" with higher genus, usually considered as tilings of the Euclidean or hyperbolic plane.
So the question is why these cannot be realized as geometry objects in $\Bbb R^3$.
I will outline an approach that additionally assumes that all vertex-figures are regular polygons as well (something usually considerde when discussing regular polyhedra).
The shape of a regular polyhedron (in your more general sense) is completely determined by two numbers $p,q\ge 3$, so that at each vertex meet $q$ regular $p$-gons.
It is a classical result, that for $1/p+1/q>1/2$, one obtains a convex regular polyhedron.
In the case $1/p+1/q=1/2$, the vertex neighborhood becomes "flat", and since it is flat at every vertex, it can never close to a bounded object.

There is a more general argument that shows that $1/p+1/q\le 1/2$ is not possible.
It can be shown that because the regular polyhedron is build in such a uniform way (all vertices look the same, all faces too), that it is in fact vertex-transitive, that is, each vertex can be mapped to any other one by a symmetry of the polyhedron.
For a bounded object these symmetries cannot involve translation, but only orthogonal transformation (assuming that the polyhedron is centered around the origin). But then, all vertices must lie on a common sphere.
Hopefully it becomes clear from above picture, that this is not possible if we try to arrange too many faces around a vertex.
And "too many" coincides exactly with $1/p+1/q\le 1/2$.
All this can be made precise, but it takes some care and sometimes tricky geometric arguments which are easier understood by visual inspection (e.g. to show that no such sphere exists).
A: I like the graph theory based argument. Let's talk about a simplicial 2-complex (hence complex) with $V$ vertices, $E$ edges, and $F$ faces, all greater than 0. A complex is regular if all vertices have the same degree $p$ and all faces have the same degree $q$ (here a face's degree is the number of edges--or 1-simplices--on its boundary). We won't allow degenerate faces, or faces whose degree is 2, so $q \geq 3$. We also don't want to allow a vertex next to only two faces, so $p \geq 3$.
Also, by the handshaking lemma, $2E = pV$ and $2E = qF$, or $V=\frac{2E}{p}$ and $F = \frac{2E}{q}$. 
Euler's theorem is that $V - E + F = \chi$, which after substituion from above becomes
$$\frac{2E}{p} - E + \frac{2E}{q} = \chi$$
$$\Rightarrow \frac{1}{p} + \frac{1}{q} = \frac{1}{2} + \frac{\chi}{2E}$$
We now consider what integer values of $p\geq 3$ and $q \geq 3$ can satisfy this equation. 
First look at the case where $\chi = 2$ (the sphere). In this case, we have that 
$$\frac{1}{p} + \frac{1}{q} = \frac{1}{2} + \frac{1}{E}$$
Now assume that both $p > 3$ and $q > 3$, then $\frac{1}{p} + \frac{1}{q} \leq \frac{1}{2} < \frac{1}{2} + \frac{1}{E}$ (since $E > 0$). Therefore, at least one of $p$ and $q$ is 3. Without loss of generality, if $p = 3$, and $q \geq 6$ we again arrive at a contradiction, because $\frac{1}{p} + \frac{1}{q} \leq \frac{1}{2} < \frac{1}{2} + \frac{1}{E}$. In fact, you can work out the only pairs of $(p, q)$ that work are $(3, 3)$--tetrahedron, $(3, 4)$--cube, $(4, 3)$--octahedron, $(3,5)$--dodecahedron, and $(5, 3)$--icosahedron. (I'll leave that to you to check.)
Now, let's look at the torus, $\chi = 0$. In this case we have $\frac{1}{p} + \frac{1}{q} = \frac{1}{2}$. So $p = q = 4$ and (as pointed out in the comments) $\{p, q\} = \{3, 6\}$ work. We'll need some geometry to argue that those can't be built. I think it will stem from the fact that in each case, we have exactly $2\pi$ angle around each vertex. In the case of $p = 3$ and $q = 6$, there is only one way to lay out three hexagons around an interior vertex which is for all dihedral angles to be $\pi$, which clearly leads to a contradiction.
With the higher genus tori, many more values for $p$ and $q$ may work and so the geometry is going to have to play a bigger role. 
