Why don't we use MACs to store passwords? These days, the best practice for storing passwords is to use a scheme like scrypt or bcrypt. The goal of these schemes is to make dictionary attack inefficient for an attacker but it also slows down legitimate use of the function. 

If you're doing thousands of password checks per second, there is a real world cost of this slow down.

I'm wondering why we can't simply use a MAC? You choose a random salt, $s$, for each password you want to store. You then compute: $MAC(s || password, k)$ and stores the result and the salt.

This construction operates quickly and seems to me to have superior security properties to scrypt and bcrypt. The only draw back is that we now have to securely store $k$. This limits its usefulness in some contexts but not in others. 

For password based file encryption, this scheme wouldn't be suitable but for storing passwords for a website, we can use a HSM device to keep the attacker from getting $k$.

Yet I've never seen any advice that suggest we store passwords in this way. Why is this?
As K.G. and nightcracker note, the reason we don't recommend this method of password storage is that it becomes insecure if the secret $k$ is compromised.  Given that the whole point of password hashing is to protect the passwords in the event that your server is compromised, it's generally not safe to assume that the compromise won't include the secret key $k$.

That said, obviously the safest thing to do would be to use both a key-stretching KDF (like PBKDF2, bcrypt or scrypt) and a secret key, e.g. as:

$$\rm hash = KDF( MAC( password, key ), salt ) $$

or simply as:

$$\rm hash = KDF( password \,||\, key,salt ) $$

where $\rm key$ is a secret key, $\rm salt$ is a unique per-user salt, and $\rm KDF$ is a slow key-derivation function suitable for password hashing.