For some months, KDE Connect has had difficulties detecting paired devices. I think this is a defect with the Android app, as my Linux laptop and Linux desktop detect each other flawlessly when they are on the same LAN, including when the laptop is connect via wifi rather than ethernet.
With my Pixel 7a phone however, it seems I need to click refresh both in the Android app and in the Linux client for the devices to see each other.
This is with Android app version 1.33.2. In fact, some progress seems to have been made in this version, as manually refreshing tends to reliably allow mutual detection, while in earlier versions it was more random.
Also note that this used to work much better some months (years ?) ago — sorry not to be precise, but there was a time when I did not use KDE Connect features on a regular basis.