Cement mortar is a widely used construction material for structural and nonstructural applications. Since mortar consumes large amounts of cement, replacing part of it with waste materials can improve sustainability. Waste cardboard can be burned and ground into a material suitable for partial cement replacement, while waste plastic fibers from tube-cutting processes can be utilized to reinforce cement mortar. In this study, cardboard powder ash (CPA) and tiny PVC plastic fiber (TPF) were incorporated in cement mortar by different amounts. The CPA replacement ratios were 0, 2.5, 5, and 7.5% by weight of cement, while the TPF contents were 0.25, 0.50, and 0.75% by volume of the mortar mix. The results showed that incorporating CPA and TPF reduced workability and compressive strength, while improving flexural strength and water absorption. A slight decrease in ultrasonic pulse velocity (UPV) was observed, although all mixtures remained within the good-quality mortar range. The optimum amounts of CPA and TPF were 5% and 0.25%, respectively, yielding a mortar with a compressive strength of 44.12 MPa, a flexural strength of 10.16 MPa, a UPV of 4.03 km/s, and a water absorption ratio of 4.21%. Furthermore, response surface methodology (RSM) combined with desirability function analysis was employed to simultaneously optimize all six responses. The RSM-based multi-objective optimization identified an optimal mix composition of 3.82% CPA and 0.36% TPF, demonstrating predicted values of 45.37 MPa for compressive strength at 56 days and 4.05 km/s for UPV at 56 days, with an overall desirability response of 0.663, confirming that RSM is an effective and practical tool for optimizing sustainable cement mortar formulations.