High-strength low-alloy (HSLA) steels are extensively utilized in shipbuilding and offshore structures due to their excellent strength, durability, and workability, specifically the DH-36 naval-grade variant. However, its susceptibility to cavitation erosion and corrosion, particularly in acidic and marine environments, limits its long-term performance. This study emphasizes enhancing the cavitation erosion and scratch resistance of a WC-10Co-4Cr coating on DH-36 steel by adding graphene nanoparticles (GNPs). A corrosion-resistant coating composed of WC-10Co-4Cr reinforced with 3 wt.% GNPs is applied using the high-velocity oxy-fuel (HVOF) thermal spray technique. These powders were deposited on DH-36 steel specimens that had undergone two surface treatments: sandblasting and laser surface texturing. Circular laser patterns were created using a fiber laser at two different pitch-to-diameter (p/d) ratios of 2 and 3. Cavitation erosion resistance was evaluated using ultrasonic cavitation tests by ASTM G32-16, where samples were exposed to a 3.5 wt.% NaCl solution for 600 minutes. Weight loss was measured at hourly intervals to assess erosion rates. Additionally, scratch indentation tests were performed under progressively increasing loads until coating failure, and the critical loads along with the coefficient of friction (COF) were analyzed. Results demonstrated that laser-textured surfaces, particularly those with optimized p/d ratios, significantly improved the coating’s adhesion and mechanical performance compared to sandblasted surfaces. Post-test surface damage from cavitation and scratch wear was examined using FE-SEM and XRD, confirming the superior protective performance of the graphene-reinforced WC-10Co-4Cr coating.