Coulomb's law is only valid in Electrostatics. In other words, you cannot ask questions like "What would happen if one of the charges is moved (or disappears)?" and hope to find a sensible answer using Coulomb's law. Making a charge move or "disappear" violates Electrostatics. (This is the same reason that Coulomb's law does not hold to find the force between two moving charges.)
To truly understand the force experienced on one charge due to another, you need to find the field of the second at the location of the first and use the Lorentz Force Law: $$F = q \left(\mathbf{E} + \mathbf{v}\times\mathbf{B}\right),$$
and to find the fields $\mathbf{E}$ and $\mathbf{B}$, you need to use Maxwell's Equations:
\begin{equation}
\begin{aligned}
\nabla \cdot \mathbf{E} &= \frac{\rho}{\epsilon_0}\\
\nabla \times \mathbf{E} &= -\frac{\partial \mathbf{B}}{\partial t}\\
\nabla \cdot \mathbf{B} &= 0\\
\nabla \times \mathbf{B} &= \mu_0 \mathbf{j} + \frac{1}{c^2}\frac{\partial \mathbf{E}}{\partial t}
\end{aligned}
\end{equation}
These equations tell us that disturbances in the field propagate at a speed $c$. So in other words, if charge $A$ was disturbed at a point, then the information that it has been moved will not reach charge $B$ instantaneously, but will travel at a speed $c$ from $A$ to $B$. (As should be expected, since in some sense special relativity and the constancy of the speed of light arose as a "consequence" of Electromagnetism!)
Here's another way to show that it can't be an "action at a distance" force, if you accept special relativity. Consider two inertial frames $S$ and $S'$, with $S'$ moving with respect to $S$ at a speed $v$.
Suppose in $S$ you moved charge $A$ and charge $B$ sensed its removal instantaneously. These two events would then be simultaneous, i.e. the time interval between them would be $\Delta t = 0$. However, from the relativity of simultaneity, we know that two events cannot be simultaneous in all inertial frames, and therefore in $S'$ there would be a time interval between $A$ moving to a new location and $B$ sensing it. However, this would mean that for some time interval $\Delta t'$ (according to the observer in $S'$), there was a force on charge $B$ that had no "source". But this violates the very idea of an inertial frame! And so we have a contradiction.
Thus, if we want special relativity to be true, we cannot have instantaneous forces, and this includes Coulomb's law.