
Your IT department is just as confused over licensing as most departments - they don't make the licensing very clear sometimes.
In general, if your App or a Flow that is called from your App needs a premium connection, then you need a premium license. Of course, your E3 plan already includes PowerApps license for non-premium connections.
The Per App Plan (which is really 2 apps), will cover you if your app uses the premium connectors.
This would be exactly as you calculated - $10 * 60 users / month (or $7200 per year).
As for your standalone flow, as long as the user that is running the flow has the premium license, this would be included in the Per App Plan license.
I hope this is helpful for you.