This worked for me and might not work for your.
Try it at your own risk!
$ wget -qO - 'http://archive.neon.kde.org/public.key' | sudo apt-key add -
$ sudo apt-add-repository http://archive.neon.kde.org/user
$ sudo apt-get update
$ sudo apt-get install neon-desktop
Upgrade everything. Repeat if necessary, until everything is really up to date and you have no held-back packages.
$ sudo apt-get update
$ sudo apt-get upgrade
$ sudo apt-get dist-upgrade
If anyone stumbles upon this: DO NOT TRY! There is a very high probability it will screw your plasma or sddm just like it did to me.
If it's too late and you already did screw it you could try:
sudo apt-get install --reinstall neon-desktop plasma-desktop plasma-desktop-data sddm xorg xserver-xorg-core xserver-xorg-video-akk && sudo dpkg-reconfigure sddm
Thanks to: http://askubuntu.com/questions/761358/kubuntu-doesnt-work-after-upgrade-to-16-04/761379#761379 for the idea. But still I had to go through more hoops to solve all my problems.
PS: If you want the neon LTS version (which has plasma 5.8.* not 5.9.* as of the time of writing this) then:
sudo apt-add-repository http://archive.neon.kde.org/user/lts
instead of
sudo apt-add-repository http://archive.neon.kde.org/user