À primeira vista, parece que você tem algo que nunca foi totalmente instalado. Olhe para a linha
2 not fully installed or removed.
Embora não tenha certeza, você pode ter tentado instalar o tomcat8 e ele falhou. Eu começaria de me livrar do tomcat8 se você tem certeza que não precisa disso.
apt-get remove tomcat8
Além disso, limpe o que não precisa mais. Isso remove a desordem desnecessária em sua saída (todos os pacotes linux no topo). Até te diz o que fazer para isso.
Use 'apt-get autoremove' to remove them.
Quando tiver terminado tudo isso, tente instalar o openssh-server novamente e veja o que acontece.