We investigate the temperature dependence of the spin dynamics in the pyrochlore magnet Nd$_2$Zr$_2$O$_7$ by neutron scattering experiments. At low temperature, this material undergoes a transition towards an all in - all out antiferromagnetic phase and the spin dynamics encompass a dispersion-less mode, characterized by a dynamical spin ice structure factor. Unexpectedly, this mode is found to survive above $T_{rm N} approx 300$ mK. Concomitantly, elastic correlations of the spin ice type develop. These are the signatures of a peculiar correlated paramagnetic phase which can be considered as a new example of Coulomb phase. Our observations near $T_{rm N}$ do not reproduce the signatures expected for a Higgs transition, but show reminiscent features of the all in - all out order superimposed on a Coulomb phase.