Much interest in the superconducting proximity effect in three-dimensional (3D) topological insulators (TIs) has been driven by the potential to induce Majorana bound states at the interface. Most candidate materials for 3D TI, however, are bulk metals, with bulk states at the Fermi level coexisting with well-defined surface states exhibiting spin-momentum locking. In such topological metals, the proximity effect can differ qualitatively from that in TIs. By studying a model topological metal-superconductor (TM-SC) heterostructure within the Bogoliubov-de Gennes formalism, we show that the pair amplitude reaches the naked surface, unlike in a topological insulator-superconductor (TI-SC) heterostructure where it is confined to the interface. Furthermore, we predict vortex-bound-state spectra to contain a Majorana zero mode localized at the naked surface, separated from the bulk vortex-bound-state spectra by a finite energy gap in such a TM-SC heterostructure. These naked-surface-bound modes are amenable to experimental observation and manipulation, presenting advantages of TM-SC over TI-SC. © 2014 American Physical Society.