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.

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.

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.