Experimente sudo apt-get install plasma-discover em vez de sudo apt-get install discover .
$ apt show plasma-discover
Package: plasma-discover
Version: 5.8.8-0ubuntu1~ubuntu16.04~ppa1
Priority: optional
Section: kde
Maintainer: Debian/Kubuntu Qt/KDE Maintainers <debian-qt-
[email protected]>
Installed-Size: 1,957 kB
Depends: appstream (>= 0.8), packagekit (>= 1.0), plasma-discover-common (= 5.8.8-0ubuntu1~ubuntu16.04~ppa1), qml-module-org-kde-kirigami, qml-module-org-kde-kquickcontrolsaddons, qml-module-qtgraphicaleffects, ubuntu-release-upgrader-qt, kio, libappstreamqt2, libc6 (>= 2.14), libkf5archive5 (>= 4.96.0), libkf5attica5 (>= 5.23.0), libkf5configcore5 (>= 5.24.0), libkf5configgui5 (>= 4.97.0), libkf5configwidgets5 (>= 4.96.0), libkf5coreaddons5 (>= 4.100.0), libkf5crash5 (>= 5.15.0), libkf5dbusaddons5 (>= 4.99.0), libkf5declarative5 (>= 4.96.0), libkf5i18n5 (>= 4.97.0), libkf5kiocore5 (>= 4.96.0), libkf5kiowidgets5 (>= 4.96.0), libkf5newstuff5 (>= 5.23.0), libkf5notifications5 (>= 5.3.0+git20141030.0311), libkf5service-bin, libkf5service5 (>= 4.96.0), libkf5widgetsaddons5 (>= 4.96.0), libkf5xmlgui-bin, libkf5xmlgui5 (>= 4.96.0), libpackagekitqt5-0, libqt5core5a (>= 5.6.0~beta), libqt5dbus5 (>= 5.0.2), libqt5gui5 (>= 5.6.0~beta) | libqt5gui5-gles (>= 5.6.0~beta), libqt5qml5 (>= 5.1.0), libqt5quick5 (>= 5.0.2) | libqt5quick5-gles (>= 5.0.2), libqt5widgets5 (>= 5.0.2), libqt5xml5 (>= 5.0.2), libstdc++6 (>= 4.5)
Recommends: software-properties-kde
Conflicts: plasma-discover-private, plasma-discover-updater, python3-aptdaemon.pkcompat
Breaks: libmuon (<< 4:5.6), muon-discover (<< 4:5.5.3a), muon-notifier (<< 4:5.5.3a), muon-updater (<< 4:5.5.3a), plasma-discover-common (<< 5.7.0)
Replaces: libmuon (<< 4:5.6), muon-discover (<< 4:5.5.3a), muon-notifier (<< 4:5.5.3a), muon-updater (<< 4:5.5.3a), plasma-discover-common (<< 5.7.0), plasma-discover-private, plasma-discover-updater
Download-Size: 970 kB
APT-Manual-Installed: yes
APT-Sources: http://ppa.launchpad.net/kubuntu-ppa/backports/ubuntu xenial/main amd64 Packages
Description: Discover software management suite
....
Note que a versão que eu tenho é 5.8.8 porque eu instalei o kubuntu-backports ppa que fornece muitas correções de bugs e melhorias sobre o que o Kubuntu 16.04 inicialmente vem com.
Se você confiar na versão padrão, você verá a versão 5.6.2 se você executar apt policy plasma-discover em seu terminal.