A combined biomaterial and cell-based solution to heal critical size bone defects in the craniomaxillofacial area is a promising alternative therapeutic option to improve upon autografting, the current gold standard. A shape memory polymer (SMP) scaffold, composed of biodegradable poly(ε-caprolactone) and coated with bioactive polydopamine, was evaluated with mesenchymal stromal cells (MSCs) derived from adipose (ADSC), bone marrow (BMSC), or umbilical cord (UCSC) tissue in their undifferentiated state or pre-differentiated toward osteoblasts for bone healing in a rat calvarial defect model. Pre-differentiating ADSCs and UCSCs resulted in higher new bone volume fraction (15.69% ± 1.64%) compared to empty (i.e., untreated) defects and scaffold-only (i.e., unseeded) groups (4.41% ± 1.11%). Notably, only differentiated UCSCs exhibited a significant increase in new bone volume, surpassing both undifferentiated UCSCs and unseeded scaffolds. Further, differentiated ADSCs and UCSCs had significantly higher trabecular numbers than their undifferentiated counterparts, unseeded scaffolds, and untreated defects. Although the mineral density regenerated within the unseeded scaffold surpassed that achieved with cell seeding, the connectivity of this bone was diminished, as the regenerated tissue confined itself to the spherical morphology of the scaffold pores. The SMP scaffold alone, with undifferentiated BMSCs, with undifferentiated and differentiated ADSCs, and differentiated UCSCs (29.72 ± 1.49 N) demonstrated significant osseointegration compared to empty defects (14.34 ± 2.21 N) after 12 weeks of healing when assessed by mechanical push-out testing. Based on these results and tissue availability to obtain the cells, pre-differentiated ADSCs and UCSCs emerge as particularly promising candidates when paired with the SMP scaffold for repairing critical size bone defects in the craniofacial skeleton.