<p>To accelerate the process of solid waste resource utilization, common industrial solid wastes were selected to prepare magnesium slag–steel slag-based composite cementitious materials synergistically. The cementitious material proportion scheme was designed, and the strength test was conducted to acquire the most advantageous proportion of the cementitious material. X-ray diffraction and scanning electron microscopy were utilized to analyze the hydration products and microstructure of the cementitious materials, further illuminating the strength formation process of the cementitious materials from a microscopic perspective. Based on the rheological experimental data of the filling slurry, a multi-objective optimization model with along-duct resistance and filling material cost as the objectives and the strength of all-solid waste cemented bodies at different ages as the constraints were established, and its optimal parameters were determined. The results demonstrated that the ideal proportion of magnesium slag–steel slag-based cementitious materials was 30% magnesium slag, 15% steel slag, 6% desulfurization gypsum, and 49% blast furnace slag. Including magnesium slag will help reduce the lack of hydration of steel slag and desulfurization gypsum in the initial stages, thus prolonging the hydration time and maintaining a high hydration reaction rate in the later stages. A comparative analysis revealed that the optimal proportion of the all-solid waste filling materials was a slurry concentration of 78% and a binder-to-aggregate ratio of 1:5 when using the multi-objective optimization model of the material based on the Pareto-dominated solution. The results can provide theoretical guidance for the proportion design of mine filling materials.</p>