Regarding Sheik/Greninja:
Their forward, up, and down tilts are very different. Forward and down smashes are different. N-Air, F-Air, B-Air, U-Air, and D-Air are different. Their grab pummels are visually distinct, and their throws are different. That only leaves a handful of attacks that are very visually and/or functionally similar, but that's bound to happen when you have a roster of almost 90 fighters. If it's okay for semi-clones to share even more similar animations & hitboxes with their parent, then theses two should be no worse.
(ETA: I forgot to mention their specials, but those are also different.)
Zelda/Palutena:
While I do see more similarities between them than the other two, I feel like you're still dismissing the differences that they do have too quickly. F-Tilt, U-Tilt, F-Smash, U-Smash, D-Smash, N-Air, B-Air (sort of), U-Air, D-Spec, and their throws are all different, as well as how their reflectors work. The similar moves that they do have also have some differences, like S-Spec having different properties despite both being fiery blasts -- Din's Fire is a moving projectile, but Explosive Flame is stationary. Farore's Wind and Warp can be excused somewhat by multiple other fighters also having teleportation recoveries (Sheik, Mewtwo, Meta Knight, and Greninja.), and the types of possible recovery moves being somewhat limited.
Frankly, I think Bandana Waddle Dee would intrude on Meta Knight's niche as a small-bodied weapon wielder with quick strikes. If there was no Meta Knight and just Byleth, things would be fine since Byleth uses many different weapons. But with Meta Knight, it results in glaring overlap.
Oh hey, I can finally use this for something.
Spears and swords have different strengths and weaknesses. Bandana Dee's
Kirby sets focus on thrusts in the cardinal directions (up, down, left, right; angled attacks are rare), and Meta Knight's current
Smash normals use a lot of shorter ranged sweeps. Even if Dee were fairly fast, his normal attacks would most likely be completely disjointed and he would rely more on good spacing to land hits. Not to mention that their specials would be completely different -- MK's are all moves that can be used for recover, but Dee's could focus more on Parasol & his Ground Thrust for D-Spec, which is unlike anything in MK's kit.