...but I don't understand why would I have to pay?
That redirect service is really for when you want to redirect from a wordpress.com subdomain, eg.
example.wordpress.com. And this also redirects to the same URL-path, which does not appear to be what you require (although you could potentially "fix" that with an undesirable second redirect at your new host). The fact that this costs money (apart from being sensible from a business model point of view) goes a long way to deter spammers.
If you had a paid domain at your old WordPress.com site (which I'm assuming was registered through WordPress themselves?) and you still have this domain (which you say you do) then there are other (possibly free) options available:
You will need to configure your new host to accept requests at the old domain (eg. a new VirtualHost if you have server access or an AddOn or Alias domain in something like cPanel). Some hosting accounts are single domain accounts, so this might be a paid-for extra.
As you may realise from doing this: you didn't need a new domain (unless that was what you wanted). Since you now have the old and new domains pointing to the new site.
You can now create a redirect (if required) from the old to new domain in order to canonicalise the domain. This should not cost you anything at the new host (apart from developer costs).