AES CTR mode encryption with HMAC
I'm not a security expert, so my review will focus on general best practices first.

Code structure and style

1. Imports
You can group import that belong together, e.g

from Crypto.Hash import HMAC
from Crypto.Hash import SHA256


can be written as

from Crypto.Hash import HMAC, SHA256


The Official Style Guide for Python also recommends to place import from the standard library before any third party libraries. Apart from the double import of zlib you're already following this.

2. Documentation
You started to add some kind of documentation on decrypt, so encrypt should be treated the same. The officially recommended way is to provide function documentation surrounded by """...""" like so

def decrypt(key, ciphertext):
    """Initialize counter for decryption.

    iv should be the same as the output of encrypt().
    """
   #^--- you probably also mean ciphertext here


This will also allow Python's built-in help(...) function to pick up your documentation.

3. Whitespace
You should tidy up the newlines in your code. There are often two (sometimes more) newlines within a function's body, while there are none between the imports and functions. This might be an issue from posting the code here on Code Review, but you should definitely check that. A reasonable convention many people agree on is to use two newlines to seperate functions (or imports from the following functions) and only use a single newline in function bodys to visually create logical groups of code.

The code itself

1. Exceptions
"You're not doing the right thing!" What thing you might ask? Well, ... "Read it! Find it out yourself!"
Sounds frustrating, doesn't it? Python offers a wide variety of built-in exceptions so you can easily convey the type of error that has happened, without the need to parse/read the actual error message. In your case ValueError seems to be appropriate. From the documentation:


  exception ValueError
     Raised when an operation or function receives an argument that has the right type but an inappropriate value, [...]


In case of an error on checking the HMAC, you might add your own exception derived from Exception (maybe HMACValidationError?). I will leave this as an exercise to you.

2. encrypt/decrypt
These functions look quite reasonable from what I can jugde and work the way I would expect them to work. A minor "issue" I found, is that they are not handling string encoding/decoding symmetrically. While encrypt does handle unicode strings by converting them to bytes representation before encryption, decrypt has no way of knowing that this step has taken place and will always return the raw bytes.
At the moment, I would favor an approach where the application using those functions has to take care that the input is already encoded into bytes and also decode the bytes back into a unicode string if desired. This would also be in line with not handling string values for the key, which strongly hints that there is an earlier step where those are created and possibly encoded. 

3. Security
From what I've seen on my journey through cryptoland, it is a quite common practice to simply prepend the ciphertext with the initialiation vector (IV). Password hashing functions do something similar and tend to store the salt prepended to the actual hash to have it available for validation later. Remember: the IV does not protect your ciphertext in the same way the key does, and therefore must not be handled with the same care. It instead prevents an attacker to see the same plaintext mapped the same ciphertext repeatedly, which is maybe more than you can afford to reveal.
Something similar applys to the HMAC. The security of the HMAC authentication should only rely on the secrecy of the key, and nothing else. So as long as you use a suitable HMAC implementation and a reasonably secure key, you should be good to go. Just bear in mind that an HMAC alone does not and cannot prevent all kind of attacks, e.g. HMAC alone cannot prevent replay.