The theory is that Walmart competes on the fact that it has a better supply chain and better negotiating power than smaller competitors. Since wages make up a smaller part of Walmart's costs, higher employee salaries would hurt smaller shops more. So, Walmart lobbies for higher minimum wages in areas where it faces competition from smaller retailers.Yes, a rise in the minimum wage probably will be less damaging for Wal-Mart than its competitors, so pursuing it as a public policy makes sense IF Wal-Mart cares that much about their relative position to other competitors (which it does to some extent). However, what is more important to Wal-Mart (by extension of their shareholders) is their absolute position. Diminishing their absolute position for a relative gain is a poor business move, and surely Wal-Mart knows it. Yes, Wal-Mart pays above minimum wage already, but a rise in the minimum wage will likely put upward pressure on the wages of their own labor force.
At best the relative gain argument is a tough sell, so lets go with a simpler theory, which I suggest is based on the likelihood that Wal-Mart's position on the minimum wage doesn't influence the outcome of any potential legislation. If what you say doesn't matter, then say whatever you want! In this case, you might as well as get some good PR and take the opportunity to point out to your much higher wages. If CEO H. Lee Scott, Jr.'s opinion was able to swing the outcome, then he'd be much more likely to push the button the other way.
P.S. Wal-Mart deserves a Nobel Prize.