The cement industry is an important industrial entity responsible for implementing carbon emission reduction targets. Considering the carbon trading and green certificate trading mechanisms, this paper presents a multi-stage planning approach for the constructed Cement-Industrial Integrated Energy System (Cement-IIES). Carbon reduction technologies represented by low-temperature waste heat recovery, as well as phased changes in economic and technical parameters, are considered in the model. The case study shows that the proposed method not only optimizes the design economy of the Cement-IIES but also achieves a substantial carbon emission reduction in the cement production process and energy supply system. Compared with the traditional single-stage planning, the proposed method improves the system’s economic efficiency by 13.88% and flexibly adapts to changes in policies such as “coal reform”, green certificate trading and carbon quotas. The low-temperature waste heat recovery technology helps the system energy utilization efficiency in the two stages increase by 0.45% and 0.86%, respectively, whilst oxygen-enriched combustion and carbon capture technologies can reduce the total carbon emissions by about 83%. In addition, the negative carbon emission effect of biomass gives the system access to annual benefits of CNY 3.10 × 107 and CNY 7.89 × 107 in the two stages, respectively.