[...], se eu conseguisse remove-lo completamente poderia sanar o problema, mas aparentemente ficam resquicios e quando reinstalado o problema reaparece.
Experimente desinstalar e fazer a limpeza como mostrado adiante, antes porém desmonte qualquer outra partição que não a do sistema e do home, pois se vai usar o updatedb e se outras partições estiverem montadas a indexação vai ficar enorme e inadequada para o presente propósito.
Inicialmente, se ainda estiver instalado, desinstale usando o método habitual para não subverter os registros info do apt/dpkg:
sudo apt-get -y remove --purge wps-office
Note que o comando xargs associado ao rm abaixo tem um potencial destruidor, pois irá apagar qualquer arquivo que contenha wps-office no nome, e portanto consta da lista produzida, incluindo qualquer arquivo .deb que tenha antes baixado e esteja no sistema, ou seja, mesmo o arquivo de instalação .deb será apagado e bem assim quaisquer .deb de dicionários e coisas parecidas, ainda que simples instaladores. Se preferir, faça antes uma seleção visual se há alguma arquivo que não queira que apague.
sudo updatedb
locate wps-office > /home/$USER/wps-residualfiles-list
Examine visualmente a lista produzida no arquivo wps-residualfiles-list e, se o caso, exclua dela qualquer arquivo que não queira que seja apagado.
Então mande apagar o que restou:
sudo xargs -L1 -t -i rm {} < /home/$USER/wps-residualfiles-list
Depois faça:
rm -R ~/.kingsoft ~/.config/kingsoft ~/.config/Kingsoft
No comando acima, embora esquisito, é isso mesmo, pois há três diretórios com nome kingsoft no /home, notando que o os dois primeiros é grafia normal em caixa baixa e o último o K é em caixa alta, maiúscula, ou seja, não é erro, é design do desenvolvedor.
Confirme se executou tudo corretamente fazendo novamente:
sudo updatedb
depois:
locate -i wps-office kingsoft
Deverá resultar em nada.