AWS Lambda gateway API gives error message

If you're using the latest version of Postman, you can generate the SigV4 signature automatically. The region should correspond to your API region (i.e. "us-east-1") and the service name should be "execute-api"

This is not a solution but it has helped me more than once:

Double-check that you are actually hitting an existing endpoint! Especially if you're working with AWS. AWS will return this error if you don't have the correct handler set up in your Lambda or if your API Gateway is not configured to serve this resource/verb/etc.