From my Galaxy S4 experice:
Careful because contacts filed in your Samsung Account will not be uploaded to your Google contacts via sync.
Also, when you use the export function, only those contacts saved on your device are transferred (i.e. Samsung and Google contacts are not exported).
The only way of moving all the contacts is via the "Share namecard via". In you settings you can choose to send all the contacts in a single file. So you can send a .vcf file to your email, save it locally and then export this file to Google.
Once you are happy that all your contacts are safely stored in Google, just delete all your contacts from your mobile (I disabled google sync first just to be on the safe side) and then re-sync with Google. All your contacts should now flow from google to your device.
Also, dont waste your time with Kies. It's rubbish
Disclaimer: always backup contacts between steps just to be on the safe side. Also check your backup to ensure that all addresses, emails and numbers are being saved without losses. Deleting all your contacts can result in loss of data, so make sure you have backups to revert to if the above doesnt work