Thank you for providing an easy to use test case. I was able to run it and confirm the issue.
So, I've locally build a new package with
https://salsa.debian.org/go-team/packages/golang-github-golang-protobuf-1-5/-/commit/2739999e3baf72f7e534fccc40918c8d5ce94229 included, and it seems that with your test case above, no packages are held back and the upgrade passes. My understanding is that the "Replaces" relationship give apt the hint that it is fine to remove golang-github-golang-protobuf-1-3-dev, which is the intended outcome.
In fact, all of the packages of the cloned bug no longer reference golang-github-golang-protobuf-1-3 at all. However, it is very easy to end up with a system that has golang-github-golang-protobuf-1-3-dev installed in bookworm, and we would rather have apt uninstall it for trixie ugprades in favor of golang-github-golang-protobuf-1-5.
Jochen, please let me know if I'm overlooking anything, otherwise I would upload that salsa commit tomorrow.
Thanks for looking into this.