In my case i used DynamoDB Connector. The tables were encrypted with customer managed encryption key. And queries returned the same error message.

So i just needed to extend the Connector Lambda permission with the kms:Decrypt to be able to query the tables