Since upgrading to Sonoma, I’m having the same problem moving Mail messages using Paletro and keyboard shortcuts as the OP here:
https://discussions.apple.com/thread/255277946
tl;dr: Move message to folder shortcuts do not work – they copy the message instead.
Unlike the OP, I’m not using Gmail; this is happening on an IMAP account.
If you’re on Sonoma, is this happening to you, too? If so, have you found a good workaround/fix (that doesn’t involve replacing Mail with another email app)?