Verifique se você tem o serviço Bluetooth em execução e se o BlueDevil está instalado corretamente com todas as suas dependências, incluindo o bluez. Depois disso, verifique o status do seu serviço Bluetooth.
sudo /etc/init.d/bluetooth restart
Depois disso, clique com o botão direito do mouse no seu ícone Bluetooth, no Plasma Desktop. Você deverá ver uma mensagem dizendo que o seu adaptador Bluetooth está desligado, com uma opção para ligá-lo. Faça isso.