Old iMessages not transfered to newly setup iPhone
I guess it was me signing in and out of my Apple ID from my iPhone and waiting over night that solved it.

I had the problem for maybe a week. No syncing was taking place but after I (amongst other things) did the above, my messages are back.