Heavy neutral leptons are motivated by several extensions of the Standard Model and their presence induces modifications in the lepton mixing matrix, including new Dirac and Majorana CP violating phases. It has been recently shown that these phases play an important role in lepton number and lepton flavour violating decays and transitions, with a striking impact for the predicted rates of certain observables. In this work, we now consider the potential role of the heavy neutral fermions and of the new CP violating phases in Higgs and $Z$-boson lepton flavour violating decays $H,Z\to \ell_\alpha^\pm\ell_\beta^\mp$, as well as in the corresponding CP asymmetries. In order to allow for a thorough analysis, we derive the full analytical express...