I think you are in the right direction. You can display all the provinces with get_terms() and display all the restraunts in that perticular province using loop-restraunt.php template.
One more suggestion, you might also want to add “custom-fields” in the “supports” array of register_post_type. This will enable custom fields and will be helpful in many ways.