King Calamari...
The only things you need for this battle are Mario, Geno, Toadstool, and metric tons of Maple Syrup. Mario's Super Flame seems to be "the thing" for attacking Tentacles and the Mighty Mollusk himself, King Calamari. When a tentacle steals somebody and then returns them shaking in their boots (or fashionable princess-type shoes), Toadstool's Therapy will heal them up and keep 'em healthy, too. Once you get to the point in the battle with two Tentacle bunches and the oversized pile of slimy sashimi, kill the tentacles first and never forget Toadstool's Group Hug for those low-HP moments. Play your cards right and make good use of that Maple Syrup and you might not have to use a single mushroom!