Sim, você deve ser capaz de "apenas encolher o disco do Ubuntu e sobrescrever com o Linux Mint sem problemas Grub" se estiver usando o formato de tabela de partição GPT e se suas partições forem endereçadas usando os GUIDs de partição (talvez tenha um olhe para /boot/grub/grub.cfg
apenas para ficar claro). Caso contrário, você pode ter que atualizar a configuração do grub (executar um script de detecção do grub), que também não é o fim do mundo, você deve ser capaz de fazer isso a partir de um sistema ativo.
Agora eu não sei como a instalação do Kali está rodando, mas vendo que ele é baseado no Debian ele realmente não deveria ser problema e detectar o próprio grub.