Does Coulomb's Law, with Gauss's Law, imply the existence of only three spatial dimensions?

I would say yes !

Actually some theories explaining quantum gravity use also this reasoning: gravity is a very weak interaction at a quantum level because it "leaks" into other dimensions, not observable at our scale, but that are present at this scale.

The mathematical tools are different, but if you just think about gauss's law you can imagine one explanation why additional dimensions are present in these theories.

Loosely speaking, (super)string theory considers additional spatial dimensions that are "wrapped up" (have unusual topologies of high curvature, I believe). Now it is of course complete speculation, but if these dimensions do exist, electromagnetism would not spread out much into those dimensions, hence it would appear as if there are only three dimensions still (to a very good approximation).

Saying that, your argument is more or less sound (though far from bulletproof). It certainly suggests we don't live in a 2D world, and that any possible extra dimensions are comparatively very small!

I think it is correct your appreciation if Gauss law holds in a two dimensional world, then the electrostatic force should be inversely proportional to the distance between charges. However, I'm not at all convinced that Gauss law could be true in a two-dimensional world because $F_{q}=k displaystyle frac{qq'(r-r')}{|r-r'|^{3}}$ is a consequence of a 3-dimensional space and since we derive Gauss law from such a force law (to be precise, from its electric field), we can not assume the validity of Gauss law independently from a 3-dimensional space.

Yes, absolutely. In fact, Gauss's law is generally considered to be the fundamental law, and Coulomb's law is simply a consequence of it (and of the Lorentz force law).

You can actually simulate a 2D world by using a line charge instead of a point charge, and taking a cross section perpendicular to the line. In this case, you find that the force (or electric field) is proportional to 1/r, not 1/r^2, so Gauss's law is still perfectly valid.

I believe the same conclusion can be made from experiments performed in graphene sheets and the like, which are even better simulations of a true 2D universe, but I don't know of a specific reference to cite for that.

It's more the other way around, I would say. Gauss's law, together with the fact that we live in a world with 3 spatial dimensions, requires that the force between charges falls off as 1/r^2. But there are perfectly consistent analogues of electrostatics in worlds with 2 or more spatial dimensions, which each have their own ``Coulomb's law" -- with a different falloff of force with distance.

More to the point, it's a lot more obvious that we live in a world with 3 spatial dimensions (look around!) than it is that the force between charges has an inverse-square law. So empirically, as well as theoretically, the number of spatial dimensions is more fundamental than the force law.

Yes. In fact the flux will not equal the charge density in other dimensionalities without similar modification of Coulomb's law according to the dimensionality.

In particular, in $d$ dimensions, we have that

$${underbrace{int int cdots int}_{d}}_{partial R} mathbf{E} cdot dmathbf{A} = K rho$$

over the boundary of some spatial region $R$ only if the field of a point charge (which integrates to give the field of a charge distribution) has the form

$$F_E propto frac{q_1 q_2}{r^{d-1}}$$

where $rho$ is measured as charge per unit $d$-volume.

So Gauss' law constrains - but technically does not determine - Coulomb's law. To determine it, you need some additional assumptions about symmetry and homogeneity of space and/or electromagnetic laws on top of Gauss's law, or some of the remaining Maxwell equations (and this generalization to higher dimensionalities is more difficult because they involve curls. In higher dimensionalities these become polyvectors, I believe, as in exterior algebra), in particular at least $nabla times mathbf{E} = mathbf{0}$ for electrostatics (in 3D).

Also, interestingly, I believe there are no stable bound atoms in dimensions $d > 3$ with the usual electromagnetic laws. In particular, the $r^{-3}$ Coulomb's law for 4D, and its higher analogues, lead to the Schrodinger equation having energy levels unbounded below, meaning even the quantum mechanics we know will not save an atom from collapse. Effectively, the walls of the potential well are too steep. A universe in 4D will have to operate in some other ways on rather different kinds of physical laws for them to admit stable matter, much less life, even if it has some forces that are similar to our electromagnetism.

Not necessarily, because extra-dimensional theories can be equipped with the process of dimensional reduction, which justify the disappearance of the extra dimensions at our (actual) energy scale.. "Compactification is the necessity for the supplemented dimensions to be made small and finite or `curled up'". The Coulomb's Law will be the special case of an ultimate theory at the classical level, like the Newtonian gravity for general relativity.