There were no storage locations found on the server.

Cloud storage vendor may support V3 or V4 signature version. Use appropriate switches as given below while configuring the cloud (compatible) storage.
Use 100039077 to configure S3 compatible Cloud storage. Test with -Provider "compatible-with-s3-v3" before using -Provider "compatible-with-s3-v4".
Example to configure Instance:
C:\PS> New-BECloudInstance -Name "CloudInstance0003" -Provider "compatible-with-s3-v3" -ServiceHost "s3.objectstorage.com" -SslMode "Full" -UrlStyle "Path"
BEMCLI> get-BECloudInstance
Name : CloudInstance0003
Id : 3adc80f6-4b48-4ae7-8f0e-bbd0e05d85fb
Provider : compatible-with-s3-v3
ServiceHost : s3.objectstorage.com
SslMode : Full
UrlStyle : Path
HttpPort : 80
HttpsPort : 443
Endpoint :