Does a magnet lose mass if it’s doing work? If a standard refrigerator magnet is used to hold up a piece of paper is it doing “work”? If so it would seem to me that energy would be required for that work and then by extension energy would be lost. If energy is lost then Einstein tells us that the magnet loses mass too, right? When the refrigerator magnet is released from its job of holding up the paper does it magically get this energy/mass back?
 A: Consider the example of a book sitting on a table. The book is static, though a gravitational force is acting on it, thereby pressing it to the table. Will the book lose any of its mass even if we were to leave it there for any amount of time?

If a standard refrigerator magnet is used to hold up a piece of paper is it doing “work”?

No. This is a static situation and the fact that neither the magnet or the paper are moving due to the magnet's force, means that no work is being done by the magnet's force.

If so it would seem to me that energy would be required for that work and then by extension energy would be lost.

No energy is being expended. Remember that energy is defined as the capacity to do work, and work itself is due to the action of a force over some distance $$W=\vec F_{\text{magnetic}} \cdot \Delta \vec x$$ and in this situation $\Delta \vec x = 0$ since neither the magnet or the paper are moving.
While the magnet is exerting a static (magnetic) force, no energy is being expended or lost. Obviously if you hold the magnet at some distance away from the fridge, and release it so that it immediately sticks to the fridge, then in this case work was done by the magnetic force.

If energy is lost then Einstein tells us that the magnet loses mass too, right?

An object will lose energy in this way only if it's mass is converted to energy$^1$. And once again, since no energy is lost, there cannot be any mass loss. And there is nothing relativistic about this example, so there is no need to consider Einstein's relativity.

When the refrigerator magnet is released from its job of holding up the paper does it magically get this energy/mass back?

It does not lose any energy/mass to begin with, so it will not gain anything "magically" or otherwise.

*

*There is binding energy involved as the magnet attaches itself to the fridge. I would guess that any (if any) energy/mass lost in the form of this binding energy would be so incredibly small, that it is not possible to calculate it, or even estimate it.

A: 
If a standard refrigerator magnet is used to hold up a piece of paper is it doing “work”?

No, a magnet does not do work in holding up a piece of paper. As it does no work there is no loss of energy nor mass involved in holding the paper up.

When the refrigerator magnet is released from its job of holding up the paper does it magically get this energy/mass back?

This is actually the more interesting part of the question. When you remove the magnet from the refrigerator you are doing work on the magnet+fridge system. This does, in fact, increase the energy of the magnet+fridge system. This has nothing to do with the non-existent work holding up the paper, but it is related to the potential energy of the magnet+fridge system due to the separation of the magnet and the fridge.
There is a mass deficit associated with this binding energy, but it would be hard to measure. We have measured this for other bound systems. Typical examples are for radioactive nuclei and for atoms with excited electrons.
