You wrote "If we assign a Microsoft 365 License such as an M365 E5. Does that only cover the Power Automate? Or can we use that as well for Power App. Just trying to figure out if there any license agreement that prohibits such license to be assign in a SA".
The M365 license covers both Power Apps and Power Automate with standard connectors. The issue is that Power Apps runs in the security context of the user running the app, so each user will need an M365 license. But flows triggered through scheduled and automated flows run in the context of the maker, so only the service account would need a license if you are only using standard connectors. If the flow is an instant triggered flow, like one triggered from a Power App, then it runs in the context of each user and each user would need a license.
I also want to correct something MichaelFP said " if is created outside the default environment you will need Power Apps Licenses(P1,P2, Per app or any D365)". It doesn't matter what environment the app is created in. Power Apps always run in the security context of the user, even in the default environment, so each user will need a license. But even apps created in other environments can run with just an M365 license if they only use standard connectors. What he may be referring to is that to create additional environments your tenant needs available capacity. That capacity is not included with M365 licenses. But if someone in your tenant has a premium license your admins can create additional environments and anyone with an M365 license can create and run apps in those environments using standard connectors if they have been given access to the environment. Once created environments don't require a specific license.
----------------------------------------------------------------------------------
If this Post helped you, please click "Does this answer your question" and give it a like to help others in the community find the answer too!
Paul Papanek Stork, MVP
Blog: https://www.dontpapanic.com/blog