Pumped thermal energy storage (PTES) is a promising long-duration energy storage technology. Nevertheless, PTES shows intermediate round-trip efficiency (RTE—0.5 ÷ 0.7) and significant CAPEX. sCO2 heat pumps and power cycles could reduce PTES CAPEX, particularly via reversible and flexible machines. Furthermore, the possibility to exploit freely available heat sources (such as waste heat and/or CSP inputs) could increase RTE, making the system capable of an apparent RTE > 100% as well as reducing CAPEX, avoiding the need for two TES systems. This paper analyses the potential valorization of industrial waste heat (WH) to enhance PTES thermodynamic performance as well as increase industrial energy efficiency, valorizing different levels of WH sources in the 100–400 °C temperature range. In fact, the use of additional heat, otherwise dumped into ambient surroundings, may contribute to avoiding the need for a second TES, thus enhancing plant competitiveness. Starting from an assessment of the most relevant industrial sectors to apply the proposed solution (looking at available WH and electric flexibility needed), this paper analyses the feasibility of a specific sCO2-based PTES case study, where the cycle is integrated into a cement production plant with a WH temperature of around 350 °C. It is demonstrated that the CAPEX of the proposed systems are still relevant and only a robust exploitation of the PTES in the ancillary service market could attract industrial customers’ interest in sCO2 PTES.