I had the same problem (can paste from Win 11 to Android but not vice-versa), which I've been able to fix by reinstalling everything:
On Windows:
- From the Start menu, search for Mobile Device Settings
- Make sure "allow this PC to access your mobile devices" and "Phone Link" toggles are on
- Click "Manage Devices", find your phone, and at the bottom of the toggles click Remove Device
On Android:
- Open Link to Windows in the Play Store
- Hit the Uninstall button
- After it uninstalls, the Uninstall button will be replaced with the Update button (not sure why that doesn't show up before). Tap that and it will reinstall the newest version of Link to Windows.
- Open the reinstalled app and choose to login with QR code
On Windows:
- Generate a QR code in Phone Link (if, like me, you can't find where to do this, go to aka.ms/linkphoneqr in your browser, which will open Phone Link and generate a QR code). Scan this with your phone to complete setup.
- Go back into Phone Link, go over to Settings, and re-enable Cross-device copy and paste
After following these steps, the cross-device clipboard works properly again.