You say:
The Coulomb potential comes from classical electrodynamics
but actually the Coulomb potential is predicted by quantum electrodynamics as a low energy limit. Quantum field theory describes the interactions between charged particles as the exchange of virtual particles, and it's not immediately obvious that it would lead to an inverse square law. However if you look at the scattering between e.g. two electrons and calculate the low energy limit you find the result is the Coulomb potential. You'll find the calculation in most QFT textbooks, though it's likely to be completely opaque to non-nerds.
So we expect the Coulomb potential to be an excellent approximation as long as the energies involved are low. As a rough guide we expect relativistic effects to become important when the energies are comparable to the rest mass of the charged particles, so for electrons we expect deviations from the Coulomb law at energies of around 1MeV. If you look at a hydrogen atom the lowest energy orbital is only 13.6eV or about a factor of 100,000 times less than the relativistic energy, and that's why we can use the Coulomb potential without worrying.
The very heaviest atoms, e.g. the actinides, have $1s$ electron energies greater than 0.1MeV, and for these atoms relativistic corrections are indeed significant. However they are still small enough that we start with a simple Coulombic description and then treat the relativistic effects as perturbations.