O que não é óbvio (ou instalado com o octave builddep sugerido pelo INSTALL.OCTAVE) é que o Octave quer qt4, eu tentei primeiro instalar os pacotes qt5 dev.
O que eu fiz e que funcionou foi:
sudo apt-get install libqt4-opengl-dev libqt4-private-dev libqt4pas-dev
mas ler a página com a qual você fez o link me faz acreditar que você precisa (e isso inclui os pacotes que eu já tinha instalado:
sudo apt-get install libqt4-dev libqtcore4 libqtwebkit4 libqt4-network libqtgui4 libqt4-opengl-dev
Depois disso, o ./configure funcionou bem e detectou qt.
O grande comando, suporte a tudo, o comando listado na parte inferior parece fazer a coisa certa para instalar dependências também:
sudo apt-get install gcc g++ gfortran make libblas-dev liblapack-dev libpcre3-dev libarpack2-dev libcurl4-gnutls-dev epstool libfftw3-dev transfig libfltk1.3-dev libfontconfig1-dev libfreetype6-dev libgl2ps-dev libglpk-dev libreadline-dev gnuplot-x11 libgraphicsmagick++1-dev libhdf5-serial-dev openjdk-8-jdk libsndfile1-dev llvm-dev lpr texinfo libgl1-mesa-dev libosmesa6-dev pstoedit portaudio19-dev libqhull-dev libqrupdate-dev libqscintilla2-dev libqt4-dev libqtcore4 libqtwebkit4 libqt4-network libqtgui4 libqt4-opengl-dev libsuitesparse-dev texlive libxft-dev zlib1g-dev autoconf automake bison flex gperf gzip icoutils librsvg2-bin libtool perl rsync tar
Mas isso pode facilmente instalar muito mais dependências que você realmente precisa.