É possível que sua configuração PATH seja ruim. Certifique-se de que echo $PATH como usuário não raiz liste /usr/bin e /bin e, como usuário root, também /usr/sbin e /sbin . No entanto, dpkg emite um aviso nesse caso, portanto, se esse aviso estiver ausente, esse não é o problema.
O comando locale faz parte de um pacote marcado como "essencial" ( libc-bin ). Para desinstalá-lo, você deve digitar uma frase completa no prompt de confirmação. Isso não é algo que você pode fazer por acidente.
Você pode ter removido o binário. Mais uma vez isso não acontecerá automaticamente, tem que ser uma consequência de algo que você fez durante a execução como root. Tenha cuidado ao executar como root, use apenas a conta root para fazer coisas que você não pode fazer da sua conta normal. Para reinstalar o pacote libc-bin , incluindo o comando locale , execute este comando como root:
apt-get --reinstall install libc-bin
Você não parece ter muita experiência com o Linux. O Kali Linux é uma distribuição para profissionais de segurança experientes, projetados para executar facilmente ferramentas relacionadas à segurança em uma máquina virtual. Não é projetado para uma instalação permanente e não é projetado para iniciantes. Se você não é um usuário Linux experiente, use uma distribuição mais amigável, como o elementary OS, o Linux Mint ou o Ubuntu.