The Kelvin (or Celsius) is an arbitrary temperature scale. What matters to Fermi liquids that may (or may not) undergo a transition to superfluidity is the dimensionless ratio $k_BT/E_F$, where $E_F$ is the Fermi energy. $E_F$ is a
measure of the typical kinetic energy of a fermion. It is related to the density via
$$
E_F=\frac{k_F^2}{2m}, \;\;\;\;
n=\frac{k_F^3}{3\pi^2}.
$$
In a neutron star the density is very large, and the Fermi energy of neutrons reaches 10s of MeV (M=$10^6$). Note that room temperature corresponds to about $1/40$ eV. In terms of $k_BT/E_F$ neutron stars are quite cold, with temperatures in the keV range. This means $k_BT/E_F<10^{-3}$, which is a typical regime for superfluidity to occur. Indeed, the Fermi energy of the electrons in a typical metal corresponds to a few 1000 K, and the critical temperature of conventional superconductors is at most a few 10s K.
The neutrons in a neutron star are more strongly coupled than the electrons in a metal, and neutron stars are indeed "high $T_c$" superconductors in the sense of a large critical $k_BT_c/E_F$. However, the main effect is the large $E_F$.