I went with @2disbetter 's suggestion and browsed the community a bit more, found https://community.mnt.re/t/waybar-broke-after-apt-upgrade/845 which seems related, and https://community.mnt.re/t/post-apt-upgrade-errors-tips/741.
From that I got a hunch and there were multiple waybar binaries. I changed one line in my sway config from
exec /usr/local/bin/waybar
to
exec /usr/bin/waybar
and after restarting sway, waybar is working again.
That also explains the confusion about the installed packages version being compatible with libfmt8, I assume the /usr/local/bin/waybar was compiled against that older version.