You are right. To create a complete solution to deal with holidays may be we will need a region table and a third table to create a relation between holiday and region.
But I believe we can create much simpler solution, also satisfactory, creating only one table region and placing region information on the holiday table.
In this case we would use the solution only in one country. Each national or International holiday would be associated with the local country. Each state holiday associated with appropriated state and every city holiday associated with appropriated city.
If it were necessary that a holiday is associated with two or more states or cities, because it is an exception, we would create a row in the holidays table for each one.