Tensor network states, and in particular Projected Entangled Pair States (PEPS) have been a strong ansatz for the variational study of complicated quantum many-body systems, thanks to their built-in entanglement entropy area law. In this work, we use a special kind of PEPS - Gauged Gaussian Fermionic PEPS (GGFPEPS) to find the ground state of $2+1d$ dimensional pure $Z_2$ lattice gauge theories for a wide range of coupling constants. We do so by combining PEPS methods with Monte-Carlo computations, allowing for efficient contraction of the PEPS and computation of correlation functions. Previously, such numerical computations involved the calculation of the Pfaffian of a matrix scaling with the system size, forming a severe bottleneck; in this work we show how to overcome this problem. This paves the way for applying the method we propose and benchmark here to other gauge groups, higher dimensions, and models with fermionic matter, in an efficient, sign-problem-free way.