To generate a certificate on the Apple provisioning profile website, firstly you have to generate keys on your mac, then upload the public key. Apple will generate your certificates with this key. When you download your certificates, tu be able to use them you need to have the private key.
The error "XCode could not find a valid private-key/certificate pair for this profile in your keychain." means you don't have the private key.
Maybe because your Mac was reinstalled, maybe because this key was generated on another Mac. So to be able to use your certificates, you need to find this key and install it on the keychain.
If you can not find it you can generate new keys restart this process on the provisioning profile website and get new certificates you will able to use.