Short Answer: You'd need explicit written permission from Nintendo (or copyright owner) to create a derivative work from their material and sell it commercially. Not likely to happen.
Long Answer: It depends on the band on how they handle the copyrights (and I don't know for those specific examples, though Zircon might). The only truly legal way to go about something like this is if you created a direct cover of a song and went through a licensing agency like Harry Fox to pay the original artist a licensing fee to utilize their material. Sadly, I don't think most game cover bands do this, so technically it's not kosher.
Now, as said above, you're talking about rearranging material and selling it/charging for attendance in a commercial venue. Technically, this isn't possible unless you have permission from the original artist to create a derivative version of their material. The licensing method above only applies for covers, not rearrangements. Now, if you're still set on the idea and want to make your best effort to do it properly, I guess you could call your material "covers" of the original and pay licensing fees to the copyright holder.