In this paper we consider a layered heterostructure of an Abelian topologically ordered state (TO), such as a fractional Chern insulator/quantum Hall state with an s-wave superconductor in order to explore the existence of non-Abelian defects. In order to uncover such defects we must augment the original TO by a $mathbb{Z}_2$ gauge theory sector coming from the s-wave SC. We first determine the extended TO for a wide variety of fractional quantum Hall or fractional Chern insulator heterostructures. We prove the existence of a general anyon permutation symmetry (AS) that exists in any fermionic Abelian TO state in contact with an s-wave superconductor. Physically this permutation corresponds to adding a fermion to an odd flux vortices (in units of $h/2e$) as they travel around the associated topological (twist) defect. As such, we call it a fermion parity flip AS. We consider twist defects which mutate anyons according to the fermion parity flip symmetry and show that they can be realized at domain walls between distinct gapped edges or interfaces of the TO superconducting state. We analyze the properties of such defects and show that fermion parity flip twist defects are always associated with Majorana zero modes. Our formalism also reproduces known results such as Majorana/parafermionic bound states at superconducting domain walls of topological/Fractional Chern insulators when twist defects are constructed based on charge conjugation symmetry. Finally, we briefly describe more exotic twist liquid phases obtained by gauging the AS where the twist defects become deconfined anyonic excitations.