kali-linux-headless 2021.3.0 and in turn other metapackages depend on mlocate. Unfortunately, the often much faster plocate added a "Breaks: mlocate" somewhere after 1.1.7-1, which makes it uninstallable on most Kali systems.

I am not sure if the "Breaks" is correct, but if it is changing the dependency of kali-linux-headless to "mlocate | plocate" should work if no package defines of some specific behavior that mlocate offers.