One of the big trouble avoiders wehn setting up Marketo and SFDC is to give the syn user a specific profile with the "password never expires" permission.
Now that you are in this situation, be aware that Marketo keeps trying to connect and SFDC to refuse connection until you stop this. So:
Thank you Gregoire, very helpful. I put in the new SFDC credentials and token in Marketo and was able to manually sync. For those leads that paused due to the expired password, I should expect them to sync in the next cycle?
And leads that never sync'ed (exist in Marketo only) will not be created in Marketo until you run an explicit (sync lead with SFDC) or implicit (Change program status, when the program is sync'ed) synchronization.