From what you describe you restricted network traffic to the storage account.
You need to allow app services to access it.
The option "Allow trusted Microsoft Services" does not include App Services:
https://learn.microsoft.com/en-us/azure/storage/common/storage-network-security?tabs=azure-portal#trusted-access-for-resources-registered-in-your-subscription
You need to integrate the storage account and the app service into a virtual network either using service endpoints or private endpoints.