If Debian 9 was installed from scratch, it uses the new "predictable network interface names" mechanism. If it was upgraded from an earlier version, it still uses old-style naming - and the file
/etc/udev/rules.d/70-persistent-net.rules should be present.
The timing information in your log entries indicates there is about 1.7 seconds time between the two rename operations. That would suggest there might be two mechanisms in play: the first line might be
systemd-networkd within initramfs setting up the new-style names, then the second could be when the root filesystem has been mounted and the "real" udev (as opposed to the mini-udev within initramfs) starts up.
Or, if the admins of the Hetzner cloud have implemented the legacy-style names using a different tool, it might be e.g.
/etc/rc.local running something like
nameif -s, which would read
/etc/mactab and set the interface names according to it.
Or if the Hetzner cloud is using
cloud-init as you commented, then you might want to check if the
/etc/cloud/cloud.cfg.d/custom-networking.cfg file is present. For more details, see:
cloud-init can have many possible sources of network configuration information, see: