Spin non-conservation in Coulomb interaction

The spin of the particles involved in Coulomb interaction is always conserved. Though your calculation is right, it does not contradict this fact about Coulomb interaction. The Feynman diagram you have drawn corresponds to $A_\mu\bar{\psi}\gamma^\mu\psi$. As you can see the involvement of $A_\mu$ makes the interaction an 'electromagnetic' interaction and thus is not limited only to 'electric' interaction (read Coulomb interaction). In higher order relativistic correction you should see not only electric effects but magnetic effects as well and the later effects exists independent of the Coulomb interaction. And let's ask why there should be any magnetic effects at all. These exist because of the fact that unlike in the case of Coulomb potential where the charges are at rest, we have moving charges in this particular scattering. Also recall that electric and magnetic fields are frame dependent concepts and thus if in one frame you see magnetic field it does not guarantee the existence of a magnetic field in all inertial frames. With these facts in hand let's examine the extra term that is bothering you. One of the extra terms is the following,

$$e^2\xi^{s^\prime\dagger}\frac{1}{\sqrt{p_0^\prime p_0}}i\boldsymbol{\sigma}\cdot(\mathbf{p^\prime}\times\mathbf{p})\xi^s\frac{i}{|\mathbf{p^\prime}-\mathbf{p}|^2}2\sqrt{p_0^\prime p_0}(\xi^{r^\prime\dagger}\xi^{r})_{\mathbf{k}}$$ The physical meaning of this term is not quite visible in the momentum space, so let's transit back to the position space by Fourier transforming, $$-e^2\int\frac{d^3\mathbf{q}}{(2\pi)^3}\xi^{s^\prime\dagger}\frac{1}{4m^3}i\boldsymbol{\sigma}\cdot(\mathbf{p^\prime}\times\mathbf{p})\xi^s\frac{1}{|\mathbf{q}|^2}2m(\xi^{r^\prime\dagger}\xi^{r})_{\mathbf{k}}e^{i\mathbf{q}\cdot(\mathbf{x_1}-\mathbf{x_2})}$$ where, I have set $p_0=p^\prime_0\approx m$, and $\mathbf{q}$ is the difference between the momenta of the particles, $\mathbf{q}=\mathbf{p^\prime}-\mathbf{p}=\mathbf{k}-\mathbf{k^\prime}$ and $\mathbf{x_1}$ and $\mathbf{x_2}$ are the position vectors of the two particles. Moreover, I have removed one $-i$ and divided by $4m^2$ in order to acquire potential from the amplitude due to the Born approximation. To perform the integration assume $\mathbf{p}$ to be a fixed vector and vary the vector $\mathbf{p^\prime}$ to generate all the possible $\mathbf{q}$ vectors. Now, write $\mathbf{p^\prime}=\mathbf{q}+\mathbf{p}$. Thus, the cross-product simplifies to $$\mathbf{p^\prime}\times\mathbf{p}=\mathbf{q}\times\mathbf{p}=-\mathbf{p}\times\mathbf{q}$$. Having done all these, let's do the integration, $$ \begin{align} &-e^2\frac{1}{4m^2}\int\frac{d^3\mathbf{q}}{(2\pi)^3}\xi^{s^\prime\dagger}i\boldsymbol{\sigma}\cdot(\mathbf{p^\prime}\times\mathbf{p})\xi^s\frac{1}{|\mathbf{q}|^2}2(\xi^{r^\prime\dagger}\xi^{r})_{\mathbf{k}}e^{i\mathbf{q}\cdot(\mathbf{x_1}-\mathbf{x_2})}\\ &=e^2\frac{1}{4m^2}\int\frac{d^3\mathbf{q}}{(2\pi)^3}\xi^{s^\prime\dagger}\boldsymbol{\sigma}\xi^s\cdot i(\mathbf{p}\times\mathbf{q})\frac{1}{|\mathbf{q}|^2}2\delta^{r^\prime r}e^{i\mathbf{q}\cdot(\mathbf{x_1}-\mathbf{x_2})}\\ &=2e^2\frac{1}{4m^2}\delta^{r^\prime r}\xi^{s^\prime\dagger}\boldsymbol{\sigma}\xi^s\cdot(\mathbf{p}\times\boldsymbol{\nabla}_{\mathbf{x}})\int\frac{d^3\mathbf{q}}{(2\pi)^3}\frac{1}{|\mathbf{q}|^2}e^{i\mathbf{q}\cdot\mathbf{x}} \end{align} $$ where we have called $\mathbf{x_1}-\mathbf{x_2}=\mathbf{x}$. Continuing, $$ \begin{align} &-e^2\frac{1}{4m^2}\int\frac{d^3\mathbf{q}}{(2\pi)^3}\xi^{s^\prime\dagger}i\boldsymbol{\sigma}\cdot(\mathbf{p^\prime}\times\mathbf{p})\xi^s\frac{1}{|\mathbf{q}|^2}2(\xi^{r^\prime\dagger}\xi^{r})_{\mathbf{k}}e^{i\mathbf{q}\cdot(\mathbf{x_1}-\mathbf{x_2})}\\ &=2e^2\frac{1}{4m^2}\delta^{r^\prime r}\xi^{s^\prime\dagger}\boldsymbol{\sigma}\xi^s\cdot(\mathbf{p}\times\boldsymbol{\nabla}_{\mathbf{x}})\frac{1}{4\pi|\mathbf{x}|}\\ &=-2e^2\frac{1}{4m^2}\delta^{r^\prime r}\xi^{s^\prime\dagger}\boldsymbol{\sigma}\xi^s\cdot\frac{\mathbf{p}\times \mathbf{x}}{4\pi|\mathbf{x}|^3}\\ &=-2\frac{e}{2m}\delta^{r^\prime r}\xi^{s^\prime\dagger}\frac{1}{2}\boldsymbol{\sigma}\xi^s\cdot\frac{e\frac{\mathbf{p}}{m}\times \mathbf{x}}{4\pi|\mathbf{x}|^3} \end{align} $$ Now, recall the definition of magnetic moment, $$\boldsymbol{\mu}=2\left(\frac{e}{2m}\right)\mathbf{S}$$ with setting the Lande $g$-factor to the value $2$ at the lowest order of QED perturbation. The spin operator is defined as, $$\mathbf{S}=\frac{1}{2}\boldsymbol{\sigma}$$ and $\xi^{s^\prime\dagger}\frac{1}{2}\boldsymbol{\sigma}\xi^s$ can be written as $\langle\mathbf{S}\rangle$. Now, the magnetic moment is in dot product with, $$\frac{e\frac{\mathbf{p}}{m}\times \mathbf{x}}{4\pi|\mathbf{x}|^3}$$ which is the magnetic field created due to the motion of one of the particles. This is the standard Biot-Savart law for a magnetic field due to a moving charge. Thus, the extra piece corresponds to a potential $-\langle\boldsymbol{\mu}\rangle\cdot\mathbf{B}$ due to one particle, via its magnetic moment, coupling to the magnetic field generated by the other particle's motion.

The moral of the story is, therefore, the above Feynman diagram has information not only about the lowest order Coulomb interaction but also of magnetic interactions due to particle motion and should not be compared to the Coulomb potential as a whole. For the Coulomb potential part the spin of the particles are conserved, whereas, the magnetic interactions mix the spins of the particles.