To make a negative sentence in English you need to use the auxiliary verb 'do'. So to make your second example correct it should be:
You do not have any new messages ...
Often, we contract 'do not' so that it becomes 'don't'.
Eg. You don't have any new messages ...
Your first example is correct because it uses 'no' to make the sentence negative. Therefore, 'don't' is not necessary.
You have no new messages (correct)
You don't have no new messages (incorrect)
Note, you can also 'haven't got' for this sentence. This form is more commonly used in spoken British English.
Eg You haven't got any new messages ...
Hope this helps!