We present the results of a direct-imaging survey for very large separation ($>$100 au), companions around 95 nearby young K5-L5 stars and brown dwarfs. They are high-likelihood candidates or confirmed members of the young ($lessapprox$150 Myr) $beta$ Pictoris and AB Doradus moving groups (ABDMG) and the TW Hya, Tucana-Horologium, Columba, Carina, and Argus associations. Images in $i$ and $z$ filters were obtained with the Gemini Multi-Object Spectrograph (GMOS) on Gemini South to search for companions down to an apparent magnitude of $zsim$22-24 at separations $gtrapprox$20 from the targets and in the remainder of the wide 5.5 $times$ 5.5 GMOS field of view. This allowed us to probe the most distant region where planetary-mass companions could be gravitationally bound to the targets. This region was left largely unstudied by past high-contrast imaging surveys, which probed much closer-in separations. This survey led to the discovery of a planetary-mass (9-13 $,M_{rm{Jup}}$) companion at 2000 au from the M3V star GU Psc, a highly probable member of ABDMG. No other substellar companions were identified. These results allowed us to constrain the frequency of distant planetary-mass companions (5-13 $,M_{rm{Jup}}$) to 0.84$_{-0.66}^{+6.73}$% (95% confidence) at semimajor axes between 500 and 5000 au around young K5-L5 stars and brown dwarfs. This is consistent with other studies suggesting that gravitationally bound planetary-mass companions at wide separations from low-mass stars are relatively rare.