Interstitial alloying in CrMnFeCoNi-based high-entropy alloys is known to modify their mechanical properties. Specifically, strength can be increased due to interstitial solid-solution hardening, while simultaneously affecting ductility. In this paper, first-principles calculations are carried out to analyze the impact of interstitial C atoms on CrMnFeCoNi in the fcc and the hcp phases. Our results show that C solution energies are widely spread and sensitively depend on the specific local environments. Using the computed solution-energy distributions together with statistical mechanics concepts, we determine the impact of C on the phase stability. C atoms are found to stabilize the fcc phase as compared to the hcp phase, indicating that the stacking-fault energy of CrMnFeCoNi increases due to C alloying. Using our extensive set of first-principles computed solution energies, correlations between them and local environments around the C atoms are investigated. This analysis reveals, e.g., that the local valence-electron concentration around a C atom is well correlated with its solution energy.