A search is reported for heavy resonances decaying into e$\mu$ final states in proton-proton collisions recorded by the CMS experiment at the CERN LHC at $\sqrt{s}=$ 13 TeV, corresponding to an integrated luminosity of 35.9 fb$^{-1}$. The search focuses on resonance masses above 200 GeV. With no evidence found for physics beyond the standard model in the e$\mu$ mass spectrum, upper limits are set at 95% confidence level on the product of the cross section and branching fraction for this lepton-flavor violating signal. Based on these results, resonant $\tau$ sneutrino production in R-parity violating supersymmetric models is excluded for masses below 1.7 TeV, for couplings $\lambda_{132} = \lambda_{231} = \lambda'_{311} = 0.01$. Heavy Z$'$ gauge bosons with lepton-flavor violating transitions are excluded for masses up to 4.4 TeV. The e$\mu$ mass spectrum is also interpreted in terms of non-resonant contributions from quantum black-hole production in models with one to six extra spatial dimensions, and lower mass limits are found between 3.6 and 5.6 TeV. In all interpretations used in this analysis, the results of this search improve previous limits by about 1 TeV. These limits correspond to the most sensitive values obtained at colliders.