On a Riemannian manifold, you can define the Laplace-Beltrami operator, which allows you to generalise the Poisson equation on arbitrary manifold resulting in Coulomb's law. As already pointed out, you will need to take into account topology and enforce charge neutrality for a closed manifold. For highly symmetric manifolds (sphere, plane, hyperbolic plane), you can still use the same method with Gauss' law.
For example, on a sphere with the usual induced Euclidean metric, in spherical coordinates, the Laplace-Beltrami operator is:
$$
\Delta V = \frac1{\sin\theta}\partial_\theta(\sin\theta\partial_\theta V)+\frac1{\sin^2\theta}\partial_\phi^2V
$$
You can solve the Poisson problem for two antipodal charges:
$$
V = -\frac1{2\pi}\ln[\tan(\theta/2)] \\
E = \frac1{2\pi\sin\theta}e_\theta
$$
with the sanity check:
$$
V\sim -\frac1{2\pi}\ln\theta \quad \theta\to0\\
V\sim \frac1{2\pi}\ln(\theta-\pi) \quad \theta\to\pi
$$
Recall that $\theta$ is basically the geodesic distance to one of the charges, so it is not just the logarithm of geodesic distance as for the plane. The $\frac1{2\pi}$ is the 2D analogue of the $\frac1{4\pi}$ in 3D. The most direct generalisation of Coulomb's law is to add a uniform background neutralising charge. In the case of the sphere, you would get:
$$
V = -\frac1{4\pi}\ln[\sin(\theta/2)] \\
E = \frac1{4\pi}\cot(\theta/2)e_\theta
$$
and by superposing two opposite, antipodal fields, you recover the first one.
Another classic example is the Coulomb law on a flat torus (with the same background uniform neutralising charge density caveat). There is no simple closed form formula, but there are rapidly converging series using Ewald summation.
I will end with a third example on the hyperbolic plane. It is actually the same as the sphere, just replace the circular functions by hyperbolic ones without the compact caveat:
$$
\Delta V = \frac1{\sinh\theta}\partial_\theta(\sinh\theta\partial_\theta V)+\frac1{\sinh^2\theta}\partial_\phi^2V \\
V = -\frac1{2\pi}\ln[\tanh(\theta/2)] \\
E = \frac1{2\pi\sinh\theta}e_\theta
$$
Remarkably, in hyperbolic space, the potential does decay to zero at infinity unlike in the flat plane.
Hope this helps.