I solved the issue. It looks like the default SystemCredentialStoreObject uses an EcryptedFile backend but the EncryptedFileLocation defaults to ApplicationData/Credentials in the \ $BaseDirectory, not the \$UserBaseDirectory. Presumably this is intentional as normally the credentials are shared across user accounts. In the cloud, this doesn’t work, for obvious reasons.

SystemCredentialStoreObject requires a local path, not a CloudObject, so setting the following works.

$SystemCredentialStore = SystemCredentialStoreObject[
<| "Backend"->"EncryptedFileSystem",
    "Keyring"->"System", 
    "EncryptedFileLocation"->FileNameJoin[{$UserBaseDirectory,"Application","Credentials"}]
|>]

It looks like setting $DefaultSystemCredentialStore in the cloud doesn’t work, however you can configure your cloud environment using InitializationValue to set up your credential store for you automatically by executing the following in the cloud.

InitializationValue[$SystemCredentialStore,"Local"] = SystemCredentialStoreObject[
    <| "Backend"->"EncryptedFileSystem",
        "Keyring"->"System", 
        "EncryptedFileLocation"->FileNameJoin[{$UserBaseDirectory,"Application","Credentials"}]
    |>]

This is not perhaps ideal, as it $UserBaseDirectory is not resolved at Initialization time. Also, it would be nice to store the initialization value in the Cloud persistence location, rather than the Local location in the cloud, but it seems that the Cloud location is not on the persistence path in the cloud itself,despite what this workflow suggests.