Sonic Storm: I watched the first couple minutes of that first match against a Kirby.
My advice:

stop playing WiFi. The lag was visibly bad enough that it had a real impact on the way you both played the game; like the sorts of strategies you employed, the zones which you felt were safe and the timing of when you threw out attacks. It
looked like a WiFi match and not an actual fight. He left a
lot of openings that you weren't able to exploit because of it; you'd be too busy doing some attack from too far away.
If Kirby turns into a rock, you should be able to punish him for it... that's just an experience thing with the timing. I find Fair works well because the little hop he gets (if the rock lands on the ground) goes above our grab level if you're a bit too far behind. Also if Kirby does something like his Suck on the ground, hop/spinshot over and punish (or fake it out when you know you don't quite have time to get there).
Also, you're too slow. For example, 2:23: Kirby was trying to recover and did a risky up-B way early. You're
Sonic the hedgehog, you had time to run to the edge and do an instant-ledgehog which would have resulted in his death. (Do you know how to do that? Practice it... just run to the edge and flick down+right up+left (assuming it's the right ledge).)
Sorry if that sounded harsh or smthg, that's just my thoughts, hope it helps.