Mac Pro booting to Kali Linux screen without HDD installed
Considering that you are only seeing a gray screen with no logo or symbol at all, I'd try some of these starts options, as well as macOS Recovery to repair your Macintosh HD volume if needed.

There are a few things you could do at startup.
First, you could hold Option on the keyboard immediately after powering on your Mac, and you should be presented with a screen with a list of volumes to boot you Mac from. Choose Macintosh HD from the list. Have a look at: How to set up and use an external Mac startup disk

Next, you could hold the X key immediately after powering on your Mac in order to force the machine to attempt to boot from the internal macOS volume.

Lastly, you could hold CommandR in order to access macOS Recovery. This would allow you to check your Mac's disk configuration and even repair the macOS volume if needed. In recovery mode, you can also change your startup disk:


  To quit macOS Recovery, choose Restart or Shut Down from the Apple () menu. If you want to choose a different startup disk before quitting, choose Startup Disk from the Apple menu.


Have a look at: About macOS Recovery

You can find more startup options here: Startup key combinations for Mac

UPDATE: I was able to find an answer that seems to address rEFInd allowing your Mac to boot into neither Recovery nor macOS: Kali Linux auto boot
I understand that you did remove rEFInd, but this may be worth looking into.