I think it's worth approaching your question from a bit of a different point of view. We know that the electric field is a vector field. In general, the divergence of a vector field is a measure of field sources/sinks. This is just an interpretation of a mathematical property, and applies to any vector field. We'll use the symbol rho to signify the field source.
$$\nabla\cdot \vec{E} \propto \rho$$
The constant of proportionality depends on what units you want to measure your field source in. I'll symbolize the constant as epsilon.
$$\nabla\cdot \vec{E} = \frac{\rho}{\epsilon_0}$$
Then we can integrate over an arbitrary volume.
$$\int\nabla\cdot \vec{E} dV = \int\frac{\rho}{\epsilon_0}dV=\frac{q_{encl}}{\epsilon_0}$$
where I chose the constant $q_{encl}$ to represent the volume integral of $\rho$.
Now I'll use the divergence theorem to rewrite the integral of the divergence as a surface integral.
$$\int\nabla\cdot \vec{E} dV = \oint \vec{E} \cdot d\vec{S}=\frac{q_{encl}}{\epsilon_0}$$
Now imagine a source that exists at a single point. By circular symmetry, the field must be perpendicular to a spherical surface around the point, and constant magnitude at a given distance from the point.
$$ \oint \vec{E} \cdot d\vec{S} = \oint E dS = E\oint dS=4\pi r^2 E$$
$$ 4\pi r^2 E =\frac{q_{point}}{\epsilon_0}$$
$$ E = \frac{q_{point}}{ 4\pi \epsilon_0 r^2 }$$
So that's almost coulomb's law. To finish the job, you also need to know how a force relates to the electric field. There's actually a sign ambiguity from the orientation of the surface, that I conveniently ignored. This corresponds to the arbitrary choice of which charge is positive or negative.
This is somewhat remarkable: we started with the properties of a vector field, chose arbitrary constants, chose a point source in 3 dimensions, and derived effectively coulomb's law. Gauss's law is really just a general property of vector fields, and coulomb's law follows from geometry, combined with the lorentz force. This equation, $$ E = \frac{q_{point}}{ 4\pi \epsilon_0 r^2 }$$
applies to any vector field with a point source in 3 dimensions, where the constant $\epsilon_0$ defines the units, and nothing more.
In my humble opinion, the most confusing step in this whole derivation is the use of the divergence theorem. I believe your dissatisfaction stems from how the divergence theorem can ignore sources outside the volume/surface of integration. This isn't really a problem with Gauss's law though, which holds anyways.