Within Dataverse and PP you have 2 limitations and they have levels to them.
1. The number of sequential calls you can make to a Dataverse API (SDKMessage aka Plugin) per person, per hour, per minute bla bla bla
2. The number of actions you can do inside of a Single flow, your environment, your tenant etc etc
So the reason it is failing is simply its throttling you.
How often are you calling it? And are you simply using Power Automate? You posted in Power Apps, but are you really calling it from an App or from within a Flow?
Any of them are fine and will work, but note that unbound actions and APIs are just plugins in Dataverse and have limitations on how often you can call them, the data they return and so on.
I'd have to understand your traffic patterns, but that is why you are getting the error as its making an HTTP call behind the scenes to the APi message handler that is exposed via the SDK.
If these suggestions help resolve your issue, Please consider Marking the answer as such and also maybe a like.
Thank you!
Sincerely, Michael Gernaey
