I have found an answer, long story short there is an issue from MS side regarding errors reporting to the user in Azure when MI env var is used to connect to storage account. At the beginning I have started with managed identity (AzureWebJobsStorage__accountName), after it failed and I did not receive satisfying answer on current question on SO I have decided to go with storage account keys, I have enabled keys on storage account and set AzureWebJobsStorage to connection string - after setting this env var for all 5 functions I received the error in azure function:
A collision for Host ID was detected in the configured storage account. For more information, see https://aka.ms/functions-hostid-collision.
And in fact it turned out that all of my functions have names longer than 32 characters and 2 of these functions have exactly the same 32 first characters - so the host id was duplicated.
Solution? One of 3 from https://learn.microsoft.com/en-us/azure/azure-functions/storage-considerations?tabs=azure-cli#host-id-considerations:
Use a separated storage account for each function app or slot involved in the collision.
Rename one of your function apps to a value fewer than 32 characters in length, which changes the computed host ID for the app and removes the collision.
Set an explicit host ID for one or more of the colliding apps. To learn more, see Host ID override.
I have decided to go with last option to avoid losing MI connection (I have to request such identities setup from IT department). So for all of 5 function apps I have generated lower case guid, removed dashes and set env var AzureFunctionsWebHost__hostid in each app to different guid.
To summarize - the main issue was that when MI env var AzureWebJobsStorage__accountName was set, Azure was throwing general error (and that error was not always thrown, it was random if it appeared or not) stating something like InternalServerError, it was not telling me what is wrong - I had to set AzureWebJobsStorage to connection string to actually see exact problem root cause.
I will report this invalid error reporting to MS