Using atomic-scale first-principles energy calculations, we describe a methodology allowing to investigate the effect of metallic elements in frequently encountered Cr23C6 carbides, and its application to the equilibrium between Cr23C6 and AlCrFeMnMo high-entropy solid solutions. Our study reveals the importance of taking properly into account the effect of interstitial C in Cr23C6, since the latter is found to have a key-influence on the thermodynamics of the compound. Moreover, it emphasizes clear-cut trends as regards the propensity of the various metallic elements to penetrate the carbide. Finally, it illustrates the role of the chemical potentials in the high-entropy solid solution, since the latter are the key-quantities controlling the composition of Cr23C6. The tractability of the approach described here should allow easy applications to similar cases, including other chemically complex solid solutions, as well as various second-phase particles (carbides, nitrides, oxides, borides…) unavoidably formed during elaboration processes.