Disorder-free localization has been recently introduced as a mechanism for ergodicity breaking in low-dimensional homogeneous lattice gauge theories caused by local constraints imposed by gauge invariance. We show that also genuinely interacting systems in two spatial dimensions can become nonergodic as a consequence of this mechanism. This result is all the more surprising since the conventional many-body localization is conjectured to be unstable in two dimensions; hence the gauge invariance represents an alternative robust localization mechanism surviving in higher dimensions in the presence of interactions. Specifically, we demonstrate nonergodic behavior in the quantum link model by obtaining a bound on the localization-delocalization transition through a classical correlated percolation problem implying a fragmentation of Hilbert space on the nonergodic side of the transition. We study the quantum dynamics in this system by introducing the method of "variational classical networks,"an efficient and perturbatively controlled representation of the wave function in terms of a network of classical spins akin to artificial neural networks. We identify a distinguishing dynamical signature by studying the propagation of line defects, yielding different light cone structures in the localized and ergodic phases, respectively. The methods we introduce in this work can be applied to any lattice gauge theory with finite-dimensional local Hilbert spaces irrespective of spatial dimensionality.