First of all your serverless user (but not the lambda role in serverless.yml) should have the following permissions:
"ssm:GetParameter",
"ssm:GetParameters",
"ssm:DescribeParameters"

That was obvious. What was unexpected in my case is that the AWS region you’re working with should be specified in your CLI as well.
For example in Windows 7 it is stored in C:\Users\{username}\.aws\config and you should add the following lines there if you’re having the same issue:
[profile your_aws_serverless_profile_name]
region=us-east-1