Insufficient privilege when running AWS Backup from Step Function

I'm trying to start a backup job from a step function, but getting a Backup.BackupException, with this message:

Insufficient privileges to perform this action. (Service: Backup, Status Code: 403, Request ID: xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx)

My state is very simple ($.table is the ARN of a dynamoDB table):

"StartBackupJob": {
  "Type": "Task",
  "Parameters": {
    "BackupVaultName": "my-vault",
    "IamRoleArn": "arn:aws:iam::xxxxxxxxxxxx:role/aws-service-role/backup.amazonaws.com/AWSServiceRoleForBackup",
    "ResourceArn": "$.table"
  },
  "Resource": "arn:aws:states:::aws-sdk:backup:startBackupJob",
  "End": true
}

I even get this when the IAM role for the step function has full permissions. Also, if I assume this role, and use it to start a backup job from the AWS CLI with the same exact parameters, it succeeds.

Any idea what I'm doing wrong?