We consider the phase diagram of two-flavor quark matter under neutron star constraints for the case of two nonlocal, covariant quark models within the mean field approximation. In one of these models (Model I) the nonlocality arises from the regularization procedure, motivated by the instanton liquid model, whereas in the second one (Model II) a separable approximation of the one-gluon exchange interaction is applied. We find that Model II predicts a larger quark mass gap, and the corresponding critical temperature at μ = 0, T_c(0) ≃ 140 MeV, is in better agreement with recent lattice QCD results than the prediction of the standard local NJL model, which exceeds 200 MeV. For both models we have considered various coupling strengths in the scalar diquark channel, showing that different low-temperature quark matter phases can occur at intermediate densities: a normal quark matter (NQM) phase, a superconducting quark matter (2SC) phase and a mixed 2SC-NQM phase. In most cases, a narrow gapless 2SC phase region is also obtained at finite temperatures.