First, although static magnetic fields can't do work, time varying magnetic fields can. Second, whenever work is done under the influence of a static magnetic field, some external source will have to supply the energy require (as opposed to an electric field that can do work on its own).

 

Let's analyze the example, the bar magnetic picking up staples. We'll start with a simpler example: two dipole moments - current loops - pointing in the same way. Both have mass, but one is fixed and the other is directly under the the first one. Let's say the magnetic forces are greater than gravity so the fixed loop pulls the other up. So, obviously, someone did some work against the gravity, but where did the energy come from? the loop itself. While the loop is ascends, the current in both decreases, due to mutual inductance, so the loops serve as some sort of battery.

 

When you move a magnet near a staple, the staple feels a changing magnetic field that does work and changes the staple's internal energy - it makes many of the current loops in the metal point in the same direction as those in the magnet. After that both magnet and staple behave as magnetic dipoles. (actually some quantum effects such as ferromagnetism make this a bit more complicated, but the basic idea is similar)

 

Bottom line, time dependent magnetic field can do work, and static magnetic fields can take energy from other sources and use it to move things.