Você precisa fazer isso em vez disso (use um curinga):
sudo apt-get purge wine-*
Sempre tenha cuidado ao usar caracteres curinga e revise as alterações antes de aceitá-las, escolhendo "Y".
Além disso, o comando que você executou: sudo apt-cache pkgnames wine
mostra apenas uma lista de pacotes disponíveis, não arquivos ou aplicativos instalados.
Para ver os aplicativos instalados, você pode executar o seguinte:
dpkg -l | grep wine
Para ver os arquivos, execute isso:
sudo find / -name "wine*" | grep wine
Não se preocupe com os resultados dos ícones para arquivos .svg e .png, pois eles não têm nada a ver com qualquer aplicativo instalado, mas fazem parte dos conjuntos de temas de ícones.