Sr$_2$CuTeO$_6$ is a square-lattice Neel antiferromagnet with superexchange between first-neighbor $S=1/2$ Cu spins mediated by plaquette centered Te ions. Substituting Te by W, the affected impurity plaquettes have predominantly second-neighbor interactions, thus causing local magnetic frustration. Here we report a study of Sr$_2$CuTe$_{1-x}$W$_x$O$_6$ using neutron diffraction and $mu$SR techniques, showing that the Neel order vanishes already at $x = 0.025 pm 0.005$. We explain this extreme order suppression using a two-dimensional Heisenberg spin model, demonstrating that a W-type impurity induces a deformation of the order parameter that decays with distance as $1/r^2$ at temperature $T=0$. The associated logarithmic singularity leads to loss of order for any $x>0$. Order for small $x>0$ and $T>0$ is induced by weak interplane couplings. In the nonmagnetic phase of Sr$_2$CuTe$_{1-x}$W$_x$O$_6$, the $mu$SR relaxation rate exhibits quantum critical scaling with a large dynamic exponent, $z approx 3$, consistent with a random-singlet state.