During setup, if restore new phone from the backup of old phone, messages should come over to new phone. I have always had messages in iCloud sync set to Off. I still got messages to new phone, by restoring from old phone backup.
iCloud sync is not the same thing as backup. But they are interrelated. Messages for example cannot be manually turned off for a regular backup. But if you turn on iCloud sync for message, they will not be included in your regular backup.
** If you did not restore new phone from backup of old phone, should have gotten messages anyway if iCloud sync for messages was On on the Old phone (as well as new one). **
But if you had iCloud sync for messages Off on the Old phone, there will be no messages stored there to sync to new phone. In this case, your messages will be included in the old phone‘s backup.
** Edit: Didn’t see previous post when sent this. Based on reading it now, I am not sure about part in my post marked **
** Edit 2: Further research...Part marked ** in my post should work.