Well, it depends. That's where the "bait" in "bait and punish" comes from. They made you think they whiffed a laggy attack and you had time to punish, but really the move wasn't as laggy as you thought. This is probably just a matchup knowledge thing, if you don't know the relative frame data for all of their attacks, don't run in and try to punish. This is a big killer in unfamiliar matchups: you're playing against a character you never normally play against, they miss a smash attack or something, and then you think "this is my chance" and run in and get hit. There are a lot of deceptive moves like that, Ganondorf's Upsmash, for example. It has average/slowish startup, but it ends very shortly after the hitbox comes out, and it's almost impossible to punish. Most moves are balanced by either having fast startup, slow endlag (like Kirby's smashes) or slow startup, fast endlag (like MK's Fsmash, Ganondorf's Upsmash). Then there are moves that are just stupidly fast all around, like Mario's Upsmash and maybe Dsmash. Your best bet is to just be patient if you're not sure.
Otherwise, punish with what you know you can hit in time. Shorthop Bair if they're behind you and really close, dashgrab or dash attack if they're medium distance, smashes are possible depending on the distance, etc.
Let's look at your example, of Mario and Link's Dsmashes!
http://kuroganehammer.com/Smash4/Mario
http://kuroganehammer.com/Smash4/Link
Mario's front part of Dsmash hits on frame 5 and 6, and the back part hits on frame 14. The move ends on frame 44, if I"m reading this correct. That gives you 30 frames to punish it, which is exactly half a second. Actually it's even more than that, if Mario's facing you, since his front hitbox ends on frame 6, so 44-6=38 frames. Which is plenty of time if you're right next to him and powershielded the front hit, but if you're a little bit away, it can be harder. Or if you shielded it, but didn't powershield, you'll get pushed away a little, as well as a little bit of shieldstun (I don't know the exact numbers) but then dropping your shield I believe takes 7 frames. And then running over there takes X amount of frames, and then Dashgrab is frame 8, Dash Attack is frame 12, Upsmash is frame 14. So you have roughly 30 frames or less to punish (don't forget human reaction time!) dropping your shield took 7 frames at least, running over to him took at least a few frames, and dashgrab takes another 8 before it connects. So yeah, you have to have good timing, or else he can just spotdodge or whatever defensive option, and punish.
As for Link, his Dsmash hitboxes are frames 9-10 (front) and 21-22 (back). He can act on frame 50, so even though his smash comes out a little slower than Mario's, he can act out of it quicker (only 28 frames after the back hit). Also, his reach might be longer because of the sword, but more importantly, the move itself does more damage, which means more shield knockback/shieldstun. I think.
tl;dr some moves are hard to punish, don't get baited if you can help it
Kirby's best moves for baiting? Um... as far as smashes go, none of them really. I think Upsmash is his hardest smash to punish on shield, it has decent knockback and endlag, and doesn't push him INTO his opponent, like Fsmash does... but it's still punishable. Kirby's Ftilt is pretty hard to punish, I believe. Otherwise, his moves don't really have crazy shield safety, they're mostly just fairly fast, and if well-spaced, can be hard to punish, unless perfect shielded.