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

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.