Problemas com tremas (não consigo digitar no terminal + não consigo abrir arquivos)

No meu laptop, tenho o Linux Mint 18.3 instalado e agora estou enfrentando o seguinte problema:
Como alemão, tenho alguns arquivos (ou diretórios) que contêm tremas em seus nomes (o que por si só não é o problema). Se eu tentar abrir esses arquivos (por exemplo, PDFs) que contêm um trema ou estão localizados em um (sub-)diretório cujo nome contém um trema, ele não será aberto.

Por exemplo, tenho um diretório chamado Übungsblättere em algum lugar desse diretório tenho alguns arquivos PDF. Se eu tentar abrir um desses arquivos do gerenciador de arquivos, o Okular me dirá que não pode abrir .../Ãbungsblätter/..., o que me mostra que estragou o caminho ao substituir os tremas por alguns caracteres estranhos.

No entanto, se eu tiver o Okular aberto e usar seu menu para abrir o respectivo arquivo, tudo funcionará como um encanto, então o problema ocorre apenas ao tentar abrir os arquivos do meu gerenciador de arquivos (Dolphin).

Além disso, percebi que não consigo digitar tremas no meu terminal. Encontrei esta questão lidando com esse problema específico e esperava que isso também corrigisse o problema do arquivo. No entanto, esse não era o caso, embora agora eu seja capaz de digitar tremas no terminal (embora ao digitar um trema ele insira dois caracteres. Por exemplo, ao digitar ö, inserirá os dois caracteres \udcc3\udcb6(descoberto digitando öe pressionando retornar depois). Ele é exibido como um único ö, mas eu tenho que excluir explicitamente dois caracteres para que a linha de comando fique vazia novamente.

Aqui está a saída de locale:

locale: Cannot set LC_ALL to default locale: No such file or directory
LANG=de_DE.UTF-8
LANGUAGE=en_US
LC_CTYPE="de_DE.UTF-8"
LC_NUMERIC=de_DE.UTF-8
LC_TIME=nds_DE.UTF-8
LC_COLLATE="de_DE.UTF-8"
LC_MONETARY=de_DE.UTF-8
LC_MESSAGES="de_DE.UTF-8"
LC_PAPER=de_DE.UTF-8
LC_NAME=de_DE.UTF-8
LC_ADDRESS=de_DE.UTF-8
LC_TELEPHONE=de_DE.UTF-8
LC_MEASUREMENT=de_DE.UTF-8
LC_IDENTIFICATION=de_DE.UTF-8
LC_ALL=

EDIT:
Acabei de descobrir que ao abrir o respectivo PDF a partir do terminal também ocorrerá um erro semelhante ao abrir a partir do gerenciador de arquivos, mas desta vez diz que não pode abrir .../bungsbltter/...(remove completamente os tremas)

EDIT2:
Saída de locale -a:

C
C.UTF-8
de_DE.utf8
en_AG
en_AG.utf8
en_AU.utf8
en_BW.utf8
en_CA.utf8
en_DK.utf8
en_GB.utf8
en_HK.utf8
en_IE.utf8
en_IN
en_IN.utf8
en_NG
en_NG.utf8
en_NZ.utf8
en_PH.utf8
en_SG.utf8
en_US.utf8
en_ZA.utf8
en_ZM
en_ZM.utf8
en_ZW.utf8
POSIX

EDIÇÃO 3:
/etc/default/locale:

LANGUAGE=en_GB.utf8
LANG=en_US.UTF-8