How can I sync old messages between iDevices?
Generally speaking, the answer is no. Messages are saved on Apple's servers for up to 30 days, but only if the message has not been confirmed as received by the device. Even if it was still on the server, there's no way to get the server to resend it to your device. Nor is there a way to sync messages between devices.

You could save Messages history off your iPhone with something like iExplorer, but there's no way to integrate that into the Messages app on your Mac.

As far as them disappearing when you rebooted, under Messages > Preferences ensure "Save history when conversations are closed" is enabled.