Eu não tentei instalar no Ubuntu 16.04 mas eu tenho no Linux Mint 18 que é baseado no Ubuntu 16.04. Descobri que tenho que instalar o pacote kdeconnect-plasma (que traz muitas dependências) para que o KDEConnect funcione.
Para quem não sabe, abra um terminal & amp; tipo
apt install kdeconnect-plasma
Você pode ter que executar o comando como root assim
sudo apt install kdeconnect-plasma