1) To make this work, I would only need to install "Google Services Framework" and "Google Play services", so no need to install "Google Play Store", right?
No all 3 MUST be installed. Play Store is more than the store front end and includes a variety of essential libraries etc
The Play Store provides many services used by apps including Play Asset Delivery, Play Feature Delivery, in-app purchases and license checks for paid apps.
2) Is it enough to set the "Network" permission to one of those or would I need more? Or could I even avoid network access altogether (I assume not)?
Network is granted by default and any revocation of it will be dependent on what you need it installed for.
3) From privacy point of view: What data will Google have access to if I do this? I assume they would see my IP address and the actual message inside the notification and then probably some unique identifier, so all the notifications that are sent can be correlated to each other, right?
Google won't have a unique ID unless you use personalised ads as far as I am aware but yes Google will have access to IP and then any other information that you input into it and permissions you grant it.
4) Is there a better alternative to this for apps that don't implement their own mechanisms yet (e.g. ProtonMail)? To me it's crazy that local notifications are forced to be routed through the Google servers.
No it is required for ProtonMail. It is the reason I use Tutanota as they don't.