Random contacts not syncing with Google
Go to Settings > Mail, Contacts, Calendars and check if your Google account is set as the default for contacts:



For local contacts (not on Google) an option would be to export them from your phone, send them to yourself via mail, and import them to your Google account, as it appears that you cannot change a contact from one group / account to another directly on iOS.