A quick note on UEFI and legacy boot:
I have two hard drives, one Linux and one Windows 10. I typically use one or the other for extended periods, I don't swap back and forth a lot, and if I reboot I usually want it to go back to the system I'm currently using. What I did was install Windows, unplugged that hard drive, and installed Linux on the other. All this over a course of time, Windows was installed for a few months prior to Linux, everything worked perfect with legacy boot previously. When I wanted to use one, I would physically disconnect the other and connect that one, and vice versa. I didn't see a problem with this, but UEFI appearently does.
Now, booting to either hard drive, I have to use F11 to get to the UEFI boot menu, and rather than selecting the hard drive, select "UEFI: Built-in EFI Shell", then manually select grub (fs0: -> cd efi -> cd kali -> grubx64.efi) or for Windows, F11 and select "Windows Boot Manager (P0: Samsung SSD)" at which point it boots normally.
Letting it try to boot to the hard drive gives me the "No Bootable Device" message.
Turns out the problem was having the boot method set to UEFI+Legacy, which I assumed would politly take care of all my senarios. Setting it to UEFI only solved my windows problem, but Linux still had issues. I no longer had to press F11, but I would be taken directly to the UEFI Built-in EFI Shell. Halway there.
I needed to add a startup.nsh script to tell it where to look.
cd /boot/efi vim startup.nsh
now add the line fs0:\EFI\kali\grubx64.efi and save the file
When I rebooted I had a 5 second wait before the script kicked in. To fix this I hit esc to bypass the script and used Set StartupDelay 0. BOOM! No more waiting, boots directly into Kali.
Next problem, for some reason my system is booting to the UEFI (BIOS) about every other time. It lands on the UEFI gui, I hit ctrl+alt+del to reboot, and it boots into linux fine. Reboot, and it lands on the UEFI again... This doesn't happen with Windows. That may be a problem for another day.