We investigate the nature of the relation among stellar mass, star-formation rate, and gas-phase metallicity (the M$_*$-SFR-Z relation) at high redshifts using a sample of 260 star-forming galaxies at $z\sim2.3$ from the MOSDEF survey. We present an analysis of the high-redshift M$_*$-SFR-Z relation based on several emission-line ratios for the first time. We show that a M$_*$-SFR-Z relation clearly exists at $z\sim2.3$. The strength of this relation is similar to predictions from cosmological hydrodynamical simulations. By performing a direct comparison of stacks of $z\sim0$ and $z\sim2.3$ galaxies, we find that $z\sim2.3$ galaxies have $\sim0.1$ dex lower metallicity at fixed M$_*$ and SFR. In the context of chemical evolution models, this evolution of the M$_*$-SFR-Z relation suggests an increase with redshift of the mass-loading factor at fixed M$_*$, as well as a decrease in the metallicity of infalling gas that is likely due to a lower importance of gas recycling relative to accretion from the intergalactic medium at high redshifts. Performing this analysis simultaneously with multiple metallicity-sensitive line ratios allows us to rule out the evolution in physical conditions (e.g., N/O ratio, ionization parameter, and hardness of the ionizing spectrum) at fixed metallicity as the source of the observed trends with redshift and with SFR at fixed M$_*$ at $z\sim2.3$. While this study highlights the promise of performing high-order tests of chemical evolution models at high redshifts, detailed quantitative comparisons ultimately await a full understanding of the evolution of metallicity calibrations with redshift.