The main key to success is letting your rival get occupied fighting Miis, then attack the rival. Run away, rinse, and repeat. This works in general for any character.
I had five rival KOs using Wario. If I remember correctly (my replay is long since invalid) two KOs were with fully charged wafts, another two with items, and one with the bike, though it was admittedly on version 1.01. I spammed his bike on the main platform, only jumping off to grab some of the items, especially the smart bomb and POW block. Even the ray gun may aid in a cheap KO. If you are lucky, you can ride your rival's bike to limit his recovery options.
I also had way more than the needed 85 KOs to accomplish the other challenge in the same run.
Others will surely post success stories with other characters, but Wario worked best for me.