Por algum motivo, o arquivo da área de trabalho para o OpenJDK não está instalado, mesmo que este arquivo esteja listado.
$ apt-file list openjdk-8-jre | grep desktop
openjdk-8-jre: /usr/share/applications/openjdk-8-java.desktop
openjdk-8-jre: /usr/share/applications/openjdk-8-policytool.desktop
$ ls -l /usr/share/applications/openjdk-8-java.desktop
ls: cannot access /usr/share/applications/openjdk-8-java.desktop: No such file or directory
$ dpkg --get-selections | grep openjdk-8
openjdk-8-jre:amd64 install
Mas você também pode usar o Oracle Java ™:
Instale o Oracle Java (TM) com estes comandos e você tem uma entrada em aberta com :
sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer
Para selecionar seu Java padrão, use o seguinte comando.
sudo update-alternatives --config java
Mas isso não tem influência no item de menu "Abrir com"