  A recent ab initio investigation of Na-C binary compounds under moderate
pressures has uncovered a possible stable NaC$_4$ superconductor with an
estimated critical temperature up to 41K. We revisit this promising binary
system by performing a more focused exploration of Na-intercalated graphite
configurations, assessing the sensitivity of their thermodynamic stability to
density functional approximations at different (T,P) conditions, and examining
their superconducting properties with the anisotropic Migdal-Eliashberg
formalism. The combinatorial screening of possible Na arrangements reveals
additional stable stoichiometries, i.e., Na$_3$C$_{10}$, NaC$_8$, NaC$_{10}$,
and NaC$_{12}$, that redefine the previously proposed convex hulls for
pressures up to 10 GPa. The evaluation of formation enthalpies with different
van der Waals functionals indicates that the proposed compounds might not be
thermodynamically stable at zero temperature but some of them could stabilize
due to the vibrational entropy or form via cold compression if graphite is used
as a starting material. Our more rigorous modeling of the electron-phonon
coupling in NaC$_4$ confirms the material's potential for high-temperature
superconductivity, with a critical temperature reaching 48 K at 10 GPa, and
reveals a well-defined two-gap structure unusual for an electron-doped
compound. By tracking the position of the intercalant nearly free electron
states with respect to the Fermi level in viable Na-C compounds, we map out the
range of pressures and compositions needed for strong electron-phonon coupling
and identify Na$_3$C$_{10}$ as an equally promising superconductor.
