Why doesn't finite field propagation speed contradict Gauss's law?

You're right: if there were just a Coulomb field outside some expanding shell, and a different Coulomb field inside the shell, then Gauss's law wouldn't hold, as can plainly be seen by drawing a Gaussian surface that straddles the shell.

However, the shell itself contains an additional, transverse electric field. This is the pulse of radiation produced by accelerating the charge, and it ensures that the flux through the Gaussian surface is zero. To see this visually, note that having zero flux through a Gaussian surface is equivalent to an equal number of electric field lines enter and exit.

Now consider the Gaussian surface drawn in red.

Four field lines enter it radially and only one exits radially. But three extra field lines exit transversely, so the radiation field ensures that Gauss's law keeps working. (And it keeps working no matter how quickly you kick the charge: kicking it faster makes the shell narrower, but the radiation field larger as well.)

In fact, this is one of the nicest ways of deriving the radiation field; see Appendix H of Purcell and Morin, Electricity and Magnetism for a full derivation using this method.

Gauss' law holds for all classical electromagnetism, including moving sources and electromagnetic waves. Your key mistake is here:

These are not equal, so ∇⋅E≠0.

The mere fact that the two are not equal in no way implies, by itself, a violation of Gauss' law. You must actually evaluate the divergence of the field to find out if it is non-zero. It depends on the details of how it transitions from one to the other. In this case, the fact that these waves are solutions to Maxwell's equations ensures that the transition is such that Gauss' law is satisfied everywhere.

Note that while Gauss’ law is satisfied at all times, it is not the only law involved. Both Ampere’s law and Faraday’s law are also involved. Due to those as the wave actually traverses the box there are large (same size as the change in the field) transverse fields generated. These can be calculated explicitly using the Lienard Wiechert potentials.