You can try to recover them with Smart Switch (since I don't think Kies works with the S6 anymore), but it's not looking too good for you at this point
The FB integration depends on the carrier's implementation. It's supported by Samsung phones, but if the carrier removed it (by choice or by accident) on their update, then that option is gone. Either way, FB sync only updates FB information into your phone, not the other way around, so that doesn't keep your contacts saved in the cloud.
Now, if you had your contacts synced to your Google account (which, honestly, you should do, and if you didn't, please do that as soon as you get your phone ready to upload contacts again), you can just restore them from your Google account, and they're accessible on any new device you set up, including iPhones, and see and edit your Contacts on any web browser via the GMail page.