Why do I get the message that I have exceeded the number of devices despite I have free slots?

Most likely, you just didn't re-login after deleting old devices (it's necessary in order to renew account information on your device).

Please try to restart the app and then log out/log in.