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?
You cannot use the names of the flags in the Gmail API. You have to use the following codes:
has:yellow-star <=> l:^ss_sy
has:blue-star <=> l:^ss_sb
has:red-star <=> l:^ss_sr
has:orange-star <=> l:^ss_so
has:green-star <=> l:^ss_sg
has:purple-star <=> l:^ss_sp
has:red-bang <=> l:^ss_cr
has:yellow-bang <=> l:^ss_cy
has:blue-info <=> l:^ss_cb
has:orange-guillemet <=> l:^ss_co
has:green-check <=> l:^ss_cg
has:purple-question <=> l:^ss_cp
Source: http://googlesystem.blogspot.se/2008/07/gmail-superstars.html