Say that you have the Key and the MAC value that was generated from the Key using CBC. Is it possible to generate a message with just the mac and the key? If so, how would you do it?
This depends on the MAC algorithm.
With HMAC based on a secure hash function, no, there is no known way to construct a message fitting the MAC other than brute-forcing it. (If you want to find a specific message, like when you have a MAC of a message containing a password and some fixed text, brute-forcing the password might be quite feasible.)
With CMAC (a MAC-algorithm based on a block cipher), given the key and MAC value, it is usually quite easy to construct a fitting message, you even can chose all but one block of your message freely.
In general, MACs based on hash-functions are usually safe, MACs based on block ciphers not.
Have a look at the CMAC algorithm, assuming we have a full-length message (multiple of block size). In the image the length is 3 blocks.
+-----+ +-----+ +-----+ | M_1 | | M_2 | | M_3 | +-----+ +-----+ +-----+ | | | +--+ | +--->(+) +--->(+)<--|K1| | | | | | +--+ +-----+ | +-----+ | +-----+ |AES_K| | |AES_K| | |AES_K| +-----+ | +-----+ | +-----+ | | | | | +-----+ +-----+ | | +-----+ | T | +-----+
(Image modified from RFC 4493, page 5.)
Assume we know the key $K$ and the tag $T$, we did choose $M_1$ and $M_3$ arbitrarily and we now want to produce a message by finding a fitting $M_2$.
This is the formula:
$$T = E_K(E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1)$$
($K_1$ is derived from $K$.)
We can apply the decryption function on both sides:
$$D_K(T) = E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1$$
Next move the XORs over:
$$D_K(T) \oplus M_3 \oplus K_1 = E_K(E_K(M_1) \oplus M_2)$$
Apply decryption again:
$$D_K( D_K(T) \oplus M_3 \oplus K_1) = E_K(M_1) \oplus M_2$$
One more step:
$$D_K( D_K(T) \oplus M_3 \oplus K_1) \oplus E_K(M_1) = M_2$$
Of course this also works with more than three blocks and if the last block is not a full block (then we pad and XOR with another key $K_2$ at the end), as long as one block is free to choose according to the result.
The general idea is that we can move through our diagram from both sides (replacing encryption by decryption if going in the other direction) until we arrive at the one unknown block.
The moral is that a MAC with a known key doesn't give us a secure hash function, where such a result would count as a preimage-attack.