Topological insulators (TIs) having intrinsic or proximity-coupled s-wave superconductivity host Majorana zero modes (MZMs) at the ends of vortex lines. The MZMs survive up to a critical doping of the TI at which there is a vortex phase transition that eliminates the MZMs. In this work, we show that the phenomenology in higher-order topological insulators (HOTIs) can be qualitatively distinct. In particular, we find two distinct features. (i) We find that vortices placed on the gapped (side) surfaces of the HOTI, exhibit a pair of phase transitions as a function of doping. The first transition is a surface phase transition after which MZMs appear. The second transition is the well-known vortex phase transition. We find that the surface transition appears because of the competition between the superconducting gap and the local $mathcal{T}$-breaking gap on the surface. (ii) We present numerical evidence that shows strong variation of the critical doping for the vortex phase transition as the center of the vortex is moved toward or away from the hinges of the sample. We believe our work provides new phenomenology that can help identify HOTIs, as well as illustrating a promising platform for the realization of MZMs.