Let's just agree that this official looking document
http://iopscience.iop.org/0953-8984/12/45/304/pdf/0953-8984_12_45_304.pdf
from the D0 experiments website is correct, and that calcium is paramagnetic
Now, the statement that everything with "paired electrons" is diamagnetic is problematic.
We would like to say that isolated atoms, with no net electron spin are diamagnetic, because the leading effect is the coupling of the orbital angular momentum which is diamagnetic. (To even distinguish between spin and orbital momentum we need weak spin-orbit coupling). The usual estimate of the net electron spin comes from Hund's rule, which says that any unfilled shell has net electronic spin. Basically the electrons don't like being stuck together in the same atom, so they minimize their contact by making their spins parallel.
But the above applies only to isolated atoms. We can apply it to insulators as long as we keep in mind that interaction between the atomic spins can lead to all sorts of fun.
Metallic systems are a whole different ballgame. Because the electrons are delocalized, we don't have this picture of isolated atoms with little electron spins attached. The electrons are no longer trapped together in an atom, leading to net spin. Instead we have extended electrons with equal number spin up and spin down, and when we apply a magnetic field we get Pauli-paramagnetism. This is quite weak in a good metal and it competes with the also weak diamagnetism of the core electrons and such. The diamagnetism can dominate: gold and zinc are diamagnetic. Calcium by the way is metallic even though the $s$ shell is full - the $s$ and $p$ bands mix and cross so that their is a Fermi surface.
You can complicate the above paragraph in about a hundred ways, with spin-orbit coupling, by combining unlocalized electrons with localized spins, by adding disorder and interaction which try to localize the electrons or order their spins. Its a real mess. I certainly don't know enough to explain the magnetic susceptibility of the whole periodic table.