Hi LukasNespor,
Could you please share more details about the error message, when did it pop out, under Add New Connection in Browser, or when Trying to New an App with the SharePoint connections?
Please make sure the User account used for the SharePoint Connection is authorized to the SharePoint site that you would like to connect, also make sure the proper gateway is selected:

A reference:
Support for on-premises SharePoint lists
For the SharePoint site that could be accessed through Browser, could you please confirm it again with the Account used to create the SharePoint connection?
If the error message occurred when trying to create a new App with SharePoint connection, then please make sure the user account has the proper permission to access the site level which specified under the site URL.

Add some additional reference:
On-premises data gateway in PowerApps
Regards