I have been using Kdeconnect over a year now, on CachyOS which is Arch Based. But some version around 1.34.x, it broke the notification plugin. It seldom shows phone’s notifications on PC; like for example it shows a whatsapp message 1 time out of 100, and for SMS even lesser.
I am on latest version as of now (1.35.5) but it never works like it did before.
File transfer also broke earlier I think around version 1.33.x.
Forgetting the device and redoing the pairing did not help.
After updating to 1.35.5, you need to re-grant the Android app the permission to read your notifications. The UX for this was a bit awkward on my phone - it probably depends on your Android version.
Actually I tried even uninstall-reinstall-re-grant route; but it didn’t help.
By the way “restricted settings” appeared only once and it disappeared from the UI after it was granted. If you did something differently, can you please tell it step by step so I can try.