Stars are, in fact, exportable. The "Google Takeout" zip archive for Reader includes a file called starred.json, containing a list of your starred items in a JSON format that, as far as I know, nothing else reads. If whatever reader you switch to can import marked items, you can probably work up a script to convert Google's format to whatever the new reader uses.
Re:Google Reader shutting down
by surrealize on Wednesday March 13, 2013 @08:30PM
(#5372264)
Thanks! The last time I checked was when they turned my google-account-with-an-apps-domain-email-address into an actual google apps account, and I had to move my Reader data.
Re:Google Reader shutting down
by 1ManBandAccts on Saturday March 16, 2013 @08:49AM
(#5385271)
Feedly will sync over all your starred items and put them into Saved.
The only approach that I've seen to exporting stars is to use the fact that Reader will create a feed of just your starred items. Then you can view that feed in some other reader and manually mark each one there (ugh).
Edit: Oh, and the read/not read history is, AFAICT, also not exportable. And I do use this as well.