We propose utilizing the Cooper pair to induce magnetic frustration in systems of two-dimensional (2D) magnetic adatom lattices on s-wave superconducting surfaces. The competition between singlet electron correlations and the RKKY coupling is shown to lead to a variety of hidden-order states that break the point-group symmetry of the 2D adatom lattice at finite temperature. The phase diagram is constructed using a newly developed effective bond theory [M. Schecter et al., Phys. Rev. Lett. 119, 157202 (2017)], and exhibits broad regions of long-range vestigial nematic order.