Ah dear, yeah 19v-20v input is the limit for stock Wiis. Sometimes unplugging the Wii and leaving it alone for a day makes it magically work again, but if Lady Luck won't deign to smile, you may have fried a regulator or two. I'm unsure of how many components you'd need to remove to safely...
If you buy them from a genuine retailer like Digikey or Mouser, yeah the 8000 will do. Just don't buy them from any chinese sites, the vast majority of listings are shitty imitations that work as badly as the ones you've already tried.
Yeah those regulators are infamous for getting major toasty (actually catching fire) and not outputting enough current in a stable fashion.
PTH08080 regulators are what we used to use for this before the PSU and PMS were mainstream. If you don't want to wait for the BB store restock, you could...