Is using the same key for different message HMACs insecure? When using the MAC-then-Encrypt composition, would using the same key for the HMAC in each different message be insecure?
No, with a reasonable choice of hash function, HMAC can safely authenticate many messages under the same key—it is not a one-time MAC like GHASH or Poly1305.  Of course, it may be prudent to use a message sequence number so you can reject replays (and it may be necessary for your encryption scheme, e.g. if you're using AES-CTR or ChaCha).

That said, why are you making this decision instead of using an authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305?