Given no knowledge of the MAC key and that M1 != M2, it is not possible to compute MAC(K, M2) from MAC(K, M1).
More generally, it isn't possible to determine the MAC of any message you haven't already seen. (Again, without the key.) The definition of a nonce is a number which is only used once with a given key.
Bob ensures that nonces are only used once by rejecting requests unless the nonce value Alice submits is strictly increasing.
There are other problems with this protocol. I assume it's meant to be used to authenticate users. No information is transmitted besides what is basically just proof that Alice knows K.
The protocol functions a lot like a one time password scheme and has the same limitations. It doesn't prevent MITM attacks, session hijacking, or server impersonation. It is not a full communication protocol.
Sometimes people comes up with schemes like this to control locks or appliances. It is unsafe to use such a protocol with "toggle" signals. An authentication request could be blocked, leaving a user's device in the state opposite from the state they believe it is in.
It is also possible to combine blocking Alice's requests with a replay attack. One could block Alice's request to engage a lock, trespass, then play back Alice's message to make it look like the lock was engaged the whole time.
Delayed playback can be solved by Alice instead sending MACK(NA || timestamp). (As long as Alice and Bob have trusted synchronized clocks.) An acknowledgment message could allow Bob to tell Alice that the command was received. The ack would needs its own authentication tag, otherwise it could be spoofed.