Программа pdfshuffler хотя бы открывается?
Если да, то предлагаю поправить ассоциации файлов с программами.
Для этого в файловом менеджере нажать на любом pdf файле правой кнопкой мыши, перейти в свойства, и там указать через какую программу открывать формат pdf.
Если не сработает, значит нужно ковыряться в текстовых файлах, куда записываются эти ассоциации.
~/.local/share/applications/mimeapps.list
~/.local/share/applications/mimeinfo.cache