What does this protocol mean? Does this mean that the message is being added onto the hashed(message, tag) ?

m || H(m, "secret")


So the output would be something like:

"RandomMessage"+N8HqKCG01b
Yes, || means concatenation. If H means HMAC and 'secret' is a secret key then this is secure.

Usually hmac accepts key as first argument and message as second. If this protocols MACs the key using the message instead of MACing the message using the key, I don't know whether that is secure.

If H is a hash instead of a MAC, then this is insecure.