Eu reinstalei o Fedora e agora eu tenho o Windows novamente no menu de inicialização. Coisas para prestar atenção:
- A inicialização com o meio de instalação USB conectado teve 2 opções diferentes: modo Legado (BIOS) e modo UEFI. Como @TomYan apontou, eu devo ter selecionado o modo errado inicialmente, o que causou todo esse problema. Eu deveria ter prestado atenção e selecionado para inicializar o USB no modo UEFI.
Eu criei as seguintes partições, provavelmente maiores que o necessário, mas tenho espaço em disco suficiente para que não haja problemas para mim:
/boot/efi EFI System 256 MiB
/boot Ext4 768 MiB
/ Ext4 56 GiB
swap Swap 8 GiB