Power Apps premium licenses contain the rights to use Power Automate flows, when "in the context of the app" (meaning you connect the flow to data sources/targets that are used also in the app). However, Power Automate premium licenses DO NOT give you rights to run Power Apps that use premium connectors.
For typical Dataverse scenarios you'd be better off with getting the Power Apps Per User licenses. Only for scenarios where you automate processes via flows that aren't related to any app and use a premium connector, then you'd need a Power Automate premium license. Note that in such circumstances you might also leverage the Power Automate Per Flow license, if you have a high number of potential users and low number of individual flows.