Hm... My daughter has a Surface Pro 2. I might try imaging it. Worth a try!
I have not tried the Media Creation Tool yet. Going there now.
Not sure where you are with this but obviously you were still able to boot Linux USBs, **it would seem it should at least boot a Windows USB with Secure Boot Disabled regardless of the state of the Keys**.
I'm curious if you were booting the Linux USB with Secure boot enabled or disabled. If it boots with it enabled I believe we have a key issue.
I don't know if you ever tried Diskpart Clean but if the disk is really clean from using shred (assuming it was done on the entire disk and not a partition) then it would seem another indication the state of Secure Boot and the Keys is where the trouble is.
I saw a utility that would list the keys installed in db (software signed with these keys allowed) and dbx (software not allowed) and at some point that may be useful although after some reading about Secure Boot and the Keys I'll say we should probably hope that isn't necessary. I'm a bit worried, possibly paranoid, that the wrong key got into dbx. At this point I don't know how you manage these keys although I'm reading some documents that describe it and using your own keys (likely best avoided in most cases).
Could you provide any further background on the Linux install, Grub configuration, or anything that might have been done regarding Secure Boot and keys. i.e. how we got here.
Have you used Ubuntu's Boot Repair ... probably shouldn't see this page
Managing EFI Boot Loaders for Linux: Repairing Boot Repair
(However, if we have fully nuked the drive none of this should exist anymore.) This is the 3rd in a series of articles that may contain clues to solving this but AFAIK it's not clearly the answer.