How to show a very important notification on the button itself which opens it?

The label on the button must not change. This will confuse users. What you can do is keep the label constant and enhance the button with additional info accordingly. You may change the color, add additional graphics, but do not change the label.

I recommend the following :

Display a red circle on the button when new messages exists. In the circle put the number of new messages.

If it is very important to know the sender of the message then display the sender name of the first message.

I do not find the information "No previous messages" important so I recommend you to omit it. But if you must show the "no message state" then disable the button.

The Material Design guidelines recommend showing notification on icon which is a set pattern across mobile apps and even on PC web applications:

Expandable notifications are revealed by tapping an indicator icon. Actions are displayed using text only (which accommodates more characters) on a separate background color and location.

When a notification arrives, it gets added to the notification drawer.

By showing the notifications on buttons will break the pattern, and turn out to be a bad user experience. It will become worst when you think about scalability:

• What will happen when the user receives messages from Mr. A, Mr. B, Mr. C....... Mr. n?

If what you are showing the user is a notification, which are meant to appear out of the context of your app, I suggest you follow the established pattern recommended by @Dipak.

If what you are showing the user are buttons or links inside your app, then these are some ideas in case they are helpful.

From your examples, you are using informative messages combined with buttons. I think the pattern should be:

"Information" + [Action]

1. "No messages": There is no action here, only information, so a button has no purpose.
2. [Show previous messages]: Clear action inside the button. No information here (other than previous messages exist)
3. "New message from Mr. X" [Show]: The message is separated from the action. This way you can manage scalability better as @Dipak suggests

In the case of links the scenario is different because the action is [Go] or [Visit]. For links the cases would be:

1. "No messages": No link here.
2. <Previous messages>: No need to specify the action.
3. <New message from Mr. X>: No need to specify the action.

It seems this is not a button (an affordance that initiates an action or completes a form), but rather navigation (an affordance that takes the user somewhere). As such, it should not look like a button.

^{download bmml source – Wireframes created with Balsamiq Mockups}

I wonder if you need to show who it's from. Doesn't that seem to provide some reason for not checking messages? If you need to know who it's from before clicking the link, list the senders on hover.