In version 1.21.1 of kde connect, which was the last update that supported andoroid 4.4.4, it stopped working, it no longer detects linked devices or allows new devices to be linked. My device is a Samsung Tab E 9.6, the device is rooted, the problem started a while ago, previously it worked normally.
I suspect the connection logic has updated for the desktop version of KDE Connect which means older builds of the Android version of KDE Connect are no longer compatible. Would you be able to provide the version(s) of the clients that are no longer detected?