Create a checkbox field 'Mark' with a value list that only has the value "1". Hide the "1" by making the field very small. You can add your own label, i.e. "Marked".
You can then do a search, finding the records with value 1 in the field 'Mark'.
You can still show your icon by making an unstored calc field 'cDisplayMark', (result container) with the calculation:
Case ( Mark ; gIcon ; "" )
gIcon is a global field (type container) that contains your icon.
If you don't want to display the mark field but only the container, then change the field Icon into a button, with the script step:
Set Field [Mark; value: Case ( Mark ; "" ; 1)]
In case you don't display the Mark field itself you won't need the value list.
Is there a way to search on this field and have my database only display the starred records?
Not directly in that field...
Create a new calculated field with calc:
not IsEmpty ( YourContainerField )
Then make a find ( by hand or by script ) putting a 1 into that new field.
Note that I suppose that the container field may contain a star or nothing.