I'm inclined to think Sinbad got conflated in there because the movie theme was a genie, and well Sinbad was a figure from the Arabian Nights. Maybe Shazam was a lot more popular than I recall, for it to be in the minds of millions,but it's hardly a red herring when it's literally half the effect.
I don't think these connections and mistakes actually did exist in the minds of millions. I think only a small handful of people ever actually formed them organically, and they never existed at all in the minds of the alleged "millions"
until the moment someone who's trying to tell them about the Mandela effect asks them, "do you remember a movie called Shazam with Sinbad playing a genie", and it's only at that very moment that they both visualize the movie being described and spontaneously develop the impression that they have always remembered it.
Consider for instance, with the "Shazam" movie specifically, the only "memory" that anyone claims to have of the movie is the simple fact that it existed and that Sinbad was in it because "he was on the cover". And all of the discussion focuses on this cover, and how people assert they very specifically remember details like the way Sinbad was posed, and the costume he was wearing. What I've never seen from anyone who claims they remember this film's existence, is any description of an actual
scene from it, in any kind of detail. Or literally
any of the other characters or actors that were in it. You'll never see an exchange between two people who "clearly remember" this movie take the form of "Remember that one scene where X did Y to Z?" "Yeah! That was my favorite part, I've used that line all the time ever since!", because nobody has a "favorite scene" because there
are no scenes.
Likewise, there is a general consensus that, being a children's movie, the other main character was a kid, but there is no consensus or even discussion about what this kid specifically looked like for instance. That's because the prompt is always "do you remember this movie, it had Sinbad on the cover posed like
this", and there's no information about the plot or other characters for the induced confabulation to build into itself.