Strange Boot Menu

If you haven't tried already, pull power from the system, take out the drives and pull the CMOS battery. Place the clear CMOS jumper in the clear position and leave it like that over night. In the morning, put the clear CMOS jumper back in it's default position and replace the battery.

This should clear the RTC and any other non user addressable stored data in the UEFI (hopefully including the boot info).

Let us know if that sorts it.

So we know: 

1. The corruption is not coming from stored data in the UEFI

2. The drives themselves are not the problem

3. BIOS updates did not solve the issue

4. The problem persists even with no boot media connected

At this point I am going to go ahead and say you need to contact Tech Support or your place of purchase and start working on getting an RMA. If the BIOS ROM was removable you could have ordered a new BIOS chip but sadly the Gaming K4 has it's BIOS soldered to the board.

5 pages of troubleshooting with no solution 

The only other solution I can think of is using a ROM programmer (with a clip on adapter) to flash the BIOS remotely. That is a tricky prospect at the best of times and would require you purchase the necessary hardware to do it. It's a little over the top as solutions go. If your system came into my shop and was out of warranty, that is how I would resolve it but as a home user you are better off just RMAing it and getting a replacement. 

It's frustrating because the issue is actually very simple, some corrupt registers in the boot info.... 

On the up side, it seems ASRock is returning to replaceable BIOS chips on some of their newer models, sadly that doesn't help you. 

Personally, I would go about the RMA as soon as possible. You shouldn't have any trouble given how easy the issue is to fix with the right tools. I suppose you could also try taking it in to a Tech and seeing if it will be quicker/cheaper to have them remote flash the chip for you. It won't void the warranty or anything so may be worth a shot if you can find someone with the tools to do it.

All we can do is try to help, we can't solve them all sadly 

What matters is that we try