Gmail filters only act on incoming mail, not on anything you've already received.
The only time it will affect emails you already have is when you create a filter and tell it to apply to all the emails you see when you test a filter.
A workaround is to search for all the emails that are older than a particular date with the label and star that you want.
label:lists is:starred before:2011/01/20
The above will pull up all emails that are labelled with "lists," are starred and arrived in your inbox before the date of 20 January 2011. Select all, then delete and you're done.
When searching with the before:
parameter, make sure the date is in the YYYY/MM/DD format.
If you look at the URL it'll be something like this:
https://mail.google.com/mail/?shva=1#search/label%3Alists+is%3Astarred+before%3A2011%2F01%2F20
You can bookmark that to easily access the search pre-filled. However, the date is locked in and you'll just need to update that next time you want to run the next purge.