learn to cancel Up-B at the right times. you got ***** in every single video in one way or another cuz you abuse Up-B and get punished. really, in general, you are unbelievably predictable in every situation. it's so obvious when he comes in that you are going to try to roll and grab to Uthrow, if that was me you would never get the grab (also, learn to Dthrow and Uthrow into combos; your Ftilt, Dair and Uair all out prioritize and out range his so keep the fight in the air vertically as much as possible till later %s - getting as many hits as possible on MK is key to winning, otherwise he is definitely going to combo you and you definitely will lose).
at long range, you Wdee toss, which is what you're supposed to do, but it's not a good move to do once he is near sweet spot range, because it isn't that good of a move, just something to rack up damage when there's no other way. just don't bother doing it when he is approaching you and is less than half way across the stage because seeing the vids, he knows how to air dodge it and punish you. you also Ftilt way too close range. When MK gets that close, Dtilt.
you might also wanna try the Jet Hammer, especially when you get to around 135-150% because it won't hurt you beyond 150% anyway and it's his fastest KO move easily. this is mostly about learning all of his moves and using them properly. using like 4-5 moves over and over does NOT work with Dedede, it's the main reason why you are taking so long to kill a light character (hit decay). you have to use all of your moves, and they are all good, so idk why you aren't. you hardly ever Dtilt, dash attack or use any smash at all. do it more.
and against your little dodge happy friend, jab combos are full of win. i don't think you jab comboed at all, in any video. just remember that you can hold it out as long as you want to by holding A.