We don't support updating Kali from a version so old. Kali 2025.3 was released one year ago and Kali is a rolling release distribution so it receives continuous updates.
You are free to update Kali installations that old but it could give some trouble like this that you need to handle manually.

The Kali-specific package python3-pyinstaller-hooks-contrib appears to have been
superseded by pyinstaller-hooks-contrib, but the new package does not declare
Breaks/Replaces against the old name, so dpkg refuses the takeover.

That is a correct analysis. But the new package pyinstaller-hooks-contrib comes from Debian (it replaced python3-pyinstaller-hooks-contrib that was packaged in Kali). And Debian packaging doesn't carry Breaks/Replaces that are specific to Kali.

We actually had a fork of Debian's pyinstaller-hooks-contrib for a while, in order to add the needed Breaks/Replaces. But at some point we dropped the fork, because as daniruiz said above, we expect users to update their system on a regular basis. We don't have the resources (and the QA) that it would take to ensure that upgrading a old version of Kali to nowadays works. Upgrading from 2025.3 to 2026.3 (basically a 1 year leap) is not something we can support, sorry.

You better restart from scratch with a clean install, I think.

Otherwise, the workaround that you suggested should work as well.