I would recommend going with the Google calender approach as it gives the user the flexibility to add additional calenders as needed. However the design change I would make is to ensure that you explicitly call out the holiday or religious occasion of which country it is or which religion so that you dont require users to go and compare the calender overlay color with the legend to determine which country\religion it belongs to. Take the example below where Google calender tells me 26th January is the republic day, but I cant be sure which country it refers to until I check the legend.
I also would like to call out the way Google has seperated the calender task schedule with the generic holiday announcement by keeping the holiday notification at the top.

With regards to prayer times, since they can vary across regions, I would recommend the overlay approach to show the different times at which prayer might happen.
With regards to specifying if a holiday is religious or cultural, I recommend just specifying the name the holiday and keeping it at that. Some holidays are cultural and religious while some holidays are religious but can also be cultural in some parts of the country. Hence instead of trying to come up with a design to determine what is what, keep it simple and just communicate the information.
Lastly, show only the user calender as a default view and dont overlay the religious calender by default and let users enable it as needed.