Hi @Johwe32
To use Azure SQL Connector in PowerApps you do not need PowerApps Plan 1 or Plan 2 license, regular Office365 Enterprise plan is enough.
If you say it will be around 10,000 records per year I strongly suggest SQL, because it has a lot more delegable functions and works smoother than SharePoint List. For some reason I always have trouble with Apps connected with SharePoint List where sometimes they update correctly sometimes they just don’t. I have rarely had problems with my apps that use Azure SQL Database.
You cannot use Excel since at this version of PowerApps you can use maximum of 2,000 rows from excel table.
You could use CDS, however then every user that will use your app will require PowerApps Plan1. For 500 people that would be around $2,500 USD/month.
More on delegation