Está consertado!
Depois de ler um pouco mais os erros, vi isso:
ALERT: There were problems running the efibootmgr program! You may need to
rename the refind_x64.efi binary to the default name (EFI/boot/bootx64.efi
on x86-64 systems or EFI/boot/bootia32.efi on x86 systems) to have it run!
Por isso, inspecionei a pasta /EFI/
e não encontrei nenhuma pasta boot
nela.
# mkdir /media/boot/EFI/boot
# cp /media/boot/EFI/refind/refind_x64.efi /media/boot/EFI/boot/bootx64.efi
Isso funciona! refind é meio quebrado (sem ícone), mas eu posso inicializar bem.
Para restaurar os ícones e refindir o trabalho corretamente:
# cp -R /media/boot/EFI/refind/* /media/boot/EFI/boot/