In the end it really seemed to be a problem with our timezonesetting! 
- Thanks to everyone!
We have used the timezone setting “Europe/Berlin” because… this is the correct timezone for our server. But with this settings mautic puts people into the segment one day after their birthday.
Now I have tried to set the timezone setting to “UTC” and everything is fine - people with a birthday go into the segment on the correct date and the campaign works like it should.
But could this timezone change maybe destroy other campaigns that worked perfectly with the old settings? Up to now I have only tried it in a test system because of this fear.