  Sr$_2$CuTeO$_6$ is a square-lattice N\'eel 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 N\'eel 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.
