This is what we used. https://developers.google.com/gmail/api/v1/reference/users/messages/list
In order to GET emails with a red star, this is what we requested.
GET https://www.googleapis.com/gmail/v1/users/me/messages?q=has%3Ared-star&key={YOUR_API_KEY}
The result was 0. Other criteria such as is:starred, has:attachment worked just as expected, are we doing something wrong?