Using recycled concrete powder (RP) as an alternative binder can effectively reduce construction and demolition waste and contribute to developing eco-friendly repair materials. However, the effect of RP on magnesium potassium phosphate cement (MKPC) has not been sufficiently studied. In this study, MKPC pastes were prepared by replacing different contents of MgO with RP, and the evolution of the structural behavior was explained from nanoscale to microscale. The results show that incorporating an appropriate amount of RP can increase the fluidity and setting time of the MKPC mixture and improve its mechanical properties. The drying shrinkage and water resistance of MKPC specimens also improve with the increasing RP content. Incorporating an appropriate amount of RP can refine the pore structure of MKPC samples, while the generation of gel-like products can compensate for the adverse effects of reduced struvite-K content. The nanoscale characteristics of the MKPC samples also indicate that incorporating RP results in a decrease in the residual MgO and pore phase content, an increase in the content of the hydrated phase, and a decrease in the loss of the hydrated phase volume fraction due to water soaking. Upon optimizing the RP content, the MKPC mixture exhibits a lower cost and carbon footprint, with the 28-d compressive strength of the sample mixed with 10% RP increased by 7.36% relative to the plain sample, indicating that recycling RP is feasible in an eco-friendly MKPC system.