The continuous rise of the global population has driven a sharp increase in energy consumption, highlighting the urgent need for more efficient and sustainable solutions in the building sector. Phase Change Materials (PCMs) are promising candidates for thermal energy storage (TES) because they absorb and release heat during phase trans. However, these materials face limitations related to leakage, thermal conductivity, and stability within alkaline building environments. This study investigates the microencapsulation of two commercial bio-based PCMs, CrodaTherm 24W and PureTemp 25, via complex coacervation combined with spray drying, using carboxymethylcellulose (CMC) and potato proteins (PP) as shell materials, followed by a calcium carbonate coating. Encapsulation efficiencies were 89.4 ± 1.01% for CrodaTherm 24W and 87.9 ± 1.84% for PureTemp 25. Although CrodaTherm-based Microencapsulated Phase Change Material (MPCM) showed a slightly higher EE%, the highest melting enthalpy was observed for the PureTemp-based sample (63.27 J/g). CrodaTherm-based MPCM also exhibited anomalous thermal behavior, including multi-peaked crystallization upon cooling and lower-than-expected latent heat, which suggests core–shell interactions or incomplete crystallization that warrant further investigation. In contrast, PureTemp-based MPCM displayed well-defined, reproducible phase transitions and stable thermal reversibility, making it a promising candidate for TES applications in building materials.