Hello @Hydrix,
Your users can use apps with premium connectors if they have Dynamics 365 licenses that provide "Limited Use Rights". As of today, these are:

These Dynamics 365 licenses grant the users the use of premium connectors:

However, the licensing guide also states:
"Limited Power Apps use rights are included within the same environment(s) as the licensed Dynamics 365 application(s) to allow users to customize and extend Dynamics 365 applications. Use of Power Apps capabilities included with Dynamics 365 licenses must be only within the context of the licensed Dynamics 365 application. Further, the specific use rights vary by Dynamics 365 license type. "
Our interpretation of this is: You can use premium licenses, but only if you use them for business processes that are somehow related to the processes the D365 apps you licensed cover. This is somewhat ambiguous. As far as I know, there are no automatic checks to verify that your apps are actually working in the context of Dynamics 365 applications.
However, even if this is not automatically enforced, if your applications are totally unrelated to D365, technically you would need standalone licenses for the users even if they have the seeded use rights from D365.
You can find the quotes and tables above in the Power Platform Licensing Guide.