Você está certo, o pacote audex está disponível para releases anteriores (como 14.04 LTS e 16.04 LTS) .
Podemos tentar instalar este pacote a partir do repositório 16.04 LTS (xenial).
Mas seja cuidadoso e faça todos os passos abaixo:
echo "deb http://archive.ubuntu.com/ubuntu/ xenial universe" | \
sudo tee /etc/apt/sources.list.d/xenial.list
cat <<EOF | sudo tee /etc/apt/preferences.d/pin-xenial
Package: *
Pin: release a=xenial
Pin-Priority: -1000
Package: audex
Pin: release a=xenial
Pin-Priority: 1
EOF
sudo apt-get update
sudo apt-get install kde-runtime
sudo apt-get install audex -t xenial
Em seguida, tente iniciar o Audex.
E remova o repositório xenial e o arquivo de preferências:
sudo rm /etc/apt/preferences.d/pin-xenial
sudo rm /etc/apt/sources.list.d/xenial.list
sudo apt-get update