A quick thinking on how to resolve this makes me wonder if we can manage to pass some information through logical decoding that the delete is part of a partition key update. This is analogous to how we set some information locally in the tuple by setting tp.t_data->t_ctid.ip_blkid to InvalidBlockNumber.
We already do something similar for UPDATEs that change the REPLICA IDENTITY; we include the oldkey in extra WAL.
The main question is whether the required knowledge is available at a suitable level.