We report the discovery of the faintest known dwarf galaxy satellite of an LMC stellar-mass host beyond the Local Group, based on deep imaging with Subaru/Hyper Suprime-Cam. MADCASH J074238+652501-dw lies $sim$35 kpc in projection from NGC 2403, a dwarf spiral galaxy at $D$$approx$3.2 Mpc. This new dwarf has $M_{g} = -7.4pm0.4$ and a half-light radius of $168pm70$ pc, at the calculated distance of $3.39pm0.41$ Mpc. The color-magnitude diagram reveals no evidence of young stellar populations, suggesting that MADCASH J074238+652501-dw is an old, metal-poor dwarf similar to low luminosity dwarfs in the Local Group. The lack of either detected HI gas ($M_{rm HI}/L_{V} < 0.69 M_odot/L_odot$, based on Green Bank Telescope observations) or $GALEX$ NUV/FUV flux enhancement is consistent with a lack of young stars. This is the first result from the MADCASH (Magellanic Analog Dwarf Companions And Stellar Halos) survey, which is conducting a census of the stellar substructure and faint satellites in the halos of Local Volume LMC analogs via resolved stellar populations. Models predict a total of $sim$4-10 satellites at least as massive as MADCASH J074238+652501-dw around a host with the mass of NGC 2403, with 2-3 within our field of view, slightly more than the one such satellite observed in our footprint.