The Wally/Waldo books are the invention of an Englishman, so I am assuming (just because there's precious little info on this on the internet) that Wally was the original name. In BrE, a wally is someone who's a bit of an idiot. It doesn't have this meaning in AmE, and neither does Waldo, so why they felt the need to change it in the US, I'm not sure. My only guess is that they chose Waldo because it's a funny-sounding name, and that might make up for the fact that the 'dunce' connotations of the name were lost on Americans. It's also a name that's pretty much died out in the US since the 1950s. The Where's Waldo books have not, it seems, sparked a baby-naming trend. (See: Name Voyager, a fun way to waste some time.)
The family of (US) candy bars / (UK) chocolate bars made by M&M/Mars (aka Masterfoods) provide another case of onomastic mismatch between the US and UK, as the following table shows. (Hey, look at me! I figured out how to make an html table!)
|inside the bar||US||UK|
|nougat||3 Musketeers||Milky Way|
|nougat, caramel||Milky Way||Mars|
|nougat, caramel, peanuts||Snickers||until 1990: Marathon; since 1990: Snickers|
|nougat, caramel, almonds||until 2000: Mars now: Snickers Almond||n/a|
|caramel (in a pretzel shape--vague equivalents; not made by the same company)||Marathon (R.I.P.)||Cadbury Curly Wurly|
Just to be confusing, there's now an energy bar called Snickers Marathon. I have read one theory that Snickers was originally called Marathon in the UK because Snickers sounded too much like knickers (i.e. underpants).
For a visual comparison of US/UK Mars, see The Visible Mars Bar Project In general, Americans are more likely than Europeans to put Almonds in their chocolate, and Europeans are more likely to put hazelnuts in their chocolate, though you see more and more of both on both sides of the Atlantic these days. Both are delightful in their own ways.