You're right about how Kirby has a hard time trying to stay above Zelda. While Zelda's aerial mobility really isn't impressive, Kirby's is all that much worse, especially when you take into consideration the start up time on most of his aerials and the lack of reach he has relative to Zelda in the air. Oh, and when Kirby connects with an aerial it really isn't anything to worry about for the most part, but when Zelda hits, she hits hard. So trying to go head-to-head against Zelda in the air is usually poor decision.
What Kirby can do, however, is be patient. Zelda players know that F-air and B-air are very good attacks, especially against lightweight Kirby. Because of this, they will often times get overzealous in their attacks and will be on the offensive for the most part. This is actually a really good strategy because Kirby is poor at retaliation.
Don't give up hope, because there will eventually be an opening that Kirby can capitalize on. When you're able to sneak a hit in on Zelda, go for it, but don't be disappointed if you don't string it into a devastating combo or don't get a KO from it - that's just not how Kirby works. Just concentrate on avoiding her attacks and getting your hits to land. If you can f-air and follow up with a f-tilt or a u-air, so much the better, but remember to be patient and don't get hit.
Zelda is like Falcon for Kirby. She's sorta tall and likes to jump at you with an overpowered aerial that can KO you before you reach 100%. But she'll also whiff grabs (and dash attacks) if you crouch and you can avoid most of her F-smash while crouching long enough to d-tilt or d-smash her before she finishes. Your crouch will force her to either go airborne or to start using lower hitting attacks like D-smash. Most of the time she'll go for aerials, because that's what she likes to do anyway. If she stays on the ground you've already neutralized her grabs and dash attack approaches and you'll be able to d-tilt her before she can get into range for a D-smash. So, although Zelda isn't really a grabby type of character, you force your opponent into a more predictable position.
Fortunately Zelda is no where near as fast as Falcon. This is a big "advantage" for Kirby as it allows him to keep pace with her much more easily. Unfortunately she still has priority and power over Kirby, and she's not as easy to combo or ledge-gimp as Falcon is. Still, work with your strengths and try to mitigate your weaknesses.
While D-throw is a fairly safe bet to use on Zelda, it seemed to be the only throw you used. At higher percents you'll want to forgo the D-throw since she can start aiming Kicks at you immediately afterward, and while you can usually shield them safely before they land it still forces you on the defensive. It's a better idea to use a B-throw and send her off the stage, or at least put her in a less offensive position.
Kal obviously has some Kirby fighting practice; when you first used a D-throw on Zelda, she tech rolls to the right. You predicted correctly and followed her immediately after the D-throw, but Kirby is just too slow to effectively tech chase. By the time you caught up to her tech roll, she had plenty of time to sidestep your Grab. This is where the Kirby player must be a better player in the sense that you must out-think your opponent twice as much as the usual character's player has to: first with the tech-prediction and second with the follow-up. In this case, had you expected the sidestep you could have countered the dodge with a D-smash (long duration) or a Ground Hammer (start-up lag).
When recovering, don't float back where Zelda can jump up and kick you. Either come in high, or go low and come up to the ledge. Zelda is terrible at Edge Guarding, and even worse at Air Guarding - at least relative to those nasty Top Tiers. So as long as you can avoid getting KO'd by her F-air/B-air, you shouldn't have too much trouble staying alive and coming back to the ledge.
In order to get a solid KO on Zelda, you're going to have to land a B-air or U-air. U-air is the stronger of the two hits, but it also requires much more precision while B-air comes out quickly with a good duration and is much more likely to hit. It sucks that if you manage to get a u-tilt on Zelda when she's within KO range of the U-air, she's sent too high up to reach before hitstun runs out. This sort of forces Kirby to try to land a B-air or U-air directly, which is not especially fun considering you have to do it while avoiding her F-air and B-air. So, as said earlier, B-air is probably your best bet, but you can always look for a D-smash opportunity since if you sweetspot it at Kirby's feet, it should be strong enough to get a vertical KO on zelda around 125%