Sandstone cut waste and marble slurry are the two predominant construction wastes in Rajasthan. These wastes pose environmental challenges, such as soil contamination and reduced water percolation due to landfill dumping. Meanwhile, Rajasthan faces a shortage of river sand and natural aggregates for engineering applications, which must be imported from neighboring states. To address these issues, the current study explores using sandstone cut waste as fine and coarse aggregates and marble slurry as a partial cement replacement in concrete. Sandstone waste from the Indian Institute of Technology Jodhpur (IITJ) campus construction site and marble slurry from Kishangarh, Ajmer, were utilized. A M30 mix was designed for paver block production, and four paver mixes were cast with 0, 10, 20, and 30% marble slurry replacement in cement by weight, producing 42 sandstone paver blocks alongside conventional cement pavers. The pavers were tested for compressive strength, flexural strength, and water absorption at 7, 14, and 28 days. Results showed the 20% marble replacement mix achieved maximum compressive strength (57 MPa at 28 days, a 53.33% increase over conventional pavers). The 0% marble mix recorded the highest flexural strength (5.8 MPa at 28 days, a 15.81% increase), though the 20% marble mix met the minimum breaking load of 3 kN. The 20% marble mix also showed the lowest water absorption (5.7%). The analysis indicates that the sandstone paver block with 20% marble replacement is the most effective for paver production, making efficient use of sandstone and marble slurry waste while addressing environmental and resource challenges in Rajasthan.