Eu sei que apenas um paste executável ( /usr/bin/paste ) está contido em coreutils package. Você pode reinstalá-lo com:
sudo apt-get install --reinstall coreutils
Se isso não ajudar, você pode tentar o seguinte.
Geralmente não é absolutamente recomendado, mas no seu caso raro, sugiro manualmente descompactar o conteúdo do pacote deb com:
sudo dpkg -x /var/cache/apt/archives/util-linux_2.27.1-6ubuntu3.4_amd64.deb /