We show that within a recently developed nonlocal chiral quark model the critical density for a phase transition to color superconducting quark matter under neutron star conditions can be low enough for these phases to occur in compact star configurations with masses below 1.3 M_solar. We study the cooling of these objects in isolation for different values of the gravitational mass and argue that, if the quark matter phase would allow unpaired quarks, the corresponding hybrid stars would cool too fast. The comparison with observational data puts tight constraints on possible color superconducting quark matter phases. Possible candidates with diquark gaps of the order of 10 keV - 1 MeV such as the "2SC+X" and the color spin locking (CSL) phase are presented and their potential to explain features of puzzling phenomena like gamma-ray bursts and pulsar kick velocities is discussed.