Can they be rewritten? Yes. It's just code.

Replacing XS is a big deal though. That's a bigger break than syntax, because 30% of the CPAN won't work with new releases.

Nicholas Clark's Ponie work shows one way where it's difficult. Artur Bergman ran an experiment around the same time to migrate SVs to something more like Parrot's PMCs, where every data type had virtual methods in well-defined slots instead of accessor macros. That didn't go very far either. These are fundamental assumptions of perl's implementation without any encapsulation beyond C macros.

It'll be a lot of work.

The best way I've ever figured out to do this is to introduce an abstraction layer for XS that's not XS and that lets the core gradually migrate away from the XS-ish implementation, but even that's a decades-long project I fear.