How to handle a Drupal core change that have an impact in the next release of a contrib module? Reading the Drupal Changes records I found that drupal_get_message() and drupal_set_message() replaced by Messenger service so lets suppose that I have a module that use the drupal_get_message() function and I want to replace it with the new Messenger service. If I do it my module only will works starting from Drupal Core >= 8.5.

So, in this point what is the correct way to produce the next module release?

Should I restrict the next release to a specific Core version adding a comment in the release notes or should I create a new branch (lets says 8.x-2.x) to implement this changes and have two module versions like 8.x-1.x (working for Core &lt; 8.5) and 8.x-2.x (working for Core >= 8.5)?
There is no need for a new branch in your module as long as your own API doesn't change IMHO. The version definition will prevent that users update too early.
There is also no need to continue providing versions compatible with old core versions, they are no longer supported.

If it's just about deprecated usages, there's no reason to hurry, you can easily wait a few month/next core minor before starting to use it to give your users time to update. All those deprecated functions will only be removed in the 9.x branch, so you have plenty of time to update. It's different if core broke something in your module and you're forced to update asap or if there is a completely new API that you'd want to use.

See also last paragraph on PHP 7.1 requirement for Doctrine packages: Their PHP version dependency is similar to your Drupal core dependency.