Hi Pawel,
First, is the federated ArcGIS Server also the Hosting Server?
If so, on the 'Add Locator' dialog, can you try selecting 'From Existing Locator' and see if the locator is listed in the Locator Item drop-down. If it is, try adding the locator using this method.
Another suggestion is to add the locator to your portal as an item from the web.
1. Navigate to the Content page
2. Select Add Item > From the Web
3. selecting 'ArcGIS Server web service'.
4. Paste the REST URL of the locator service under the URL parameter.
5. Enter you credentials under the 'a secure service was detected' section
6. Select the 'Store credentials with service item. Do not prompt for authentication"
7. Click 'Add Item'
8. Share the locator item with the Organization
9. Under the Utility Services tab of the Organization Settings click 'Add Locator'
10. Select 'from existing locator'
11. The locator you just added should show in the drop-down
Hope this helps,
Marley