It seems to me that there is some confusion here. Coulomb Law is a law of physics.
It is about electricity. It was discovered experimentally and can be proved ONLY by experiment. It is a statement about REAL WORLD.
I am not completely sure what "Gauss Law" in the question is. But I suppose this is Gauss' THEOREM about flux. This is a mathematical theorem. Which is established by mathematical proof and logically speaking has nothing to do with electricity or anything in the real world.
I checked the Wikipedia article and it indeed shows the same confusion. These are two different things, from different realities, and one cannot follow from another. Gauss theorem applies to vector fields (which is a mathematical notion).
Gravity field, electrostatic field, are described as vector fields (this is an experimental fact) and THEREFORE must satisfy Gauss' theorem (and all other theorems about vector fields).
And of course the chronological question has trivial answer: Gauss was too young when Coulomb law was discovered.