Shadow_of_eagle I just tested this functionality on Nobara Linux KDE and Pixel 8 with up-to-date GrapheneOS, and it works. I don't remember changing any of the default settings for the KDE connect app, just allowing permissions from its "your-pc" menu, then clicking on the links under "Some Plugins need permissions to work, tap for more info". Make sure you allow permissions through that menu, not the default android permissions menu, since the app might not know it now has that permission otherwise. I have it set up to allow full file access, not Storage scopes.
If everything else fails, try a full reset of the KDE connect app - delete data or even download it again. Make sure it is the latest version (I got mine from F-Droid, KDE's own repo). My app version is 1.33.9
This is assuming everything on your Linux side is set up correctly, which I guess it is, if it's working with another phone. Still, make sure it is up-to-date. Mine is 25.08.0
Oh, and a really stupid thing to check - make sure both your PC and phone are on the same WiFi. I had issues if one is on the 2.4 GHz band, and the other on 5GHz band. If your laptop is old and doesn't support 5GHz, that might be an issue. However, if other KDE Connect features are working between the two devices, this is probably not the issue.
And make sure your phone is awake and unlocked when you try these. Just in case.
Hope this helps.