255 positions is really alot. I think, that should be more than enough, for any rewinding (or undo) function. Good work. What you mentioned about the falling, also makes sense, of course.
And also this idea with the stars is good, because the game needs something like a reward-system, that increases the motivation of the players. When the game give stars, the game also needs something like a highscore display, showing the highest star-value, achieved so far, somewhere on the screen, or in a list, at the end of the game.
Another idea to that reward-system point, could be the following. It could also be made in a way, that two separate highscore-lists would be created (that also save the scores to disk by the way), depending on the user's settings for the rewind (undo) function, in the game-menu, i.e., whether they use this function or not. If they use it, their score goes in one list, if not, it goes in the other list. The game could have a point named "highscores" in the game-menue, where the user can see the saved highscores and where the game shows both lists. At the top of each list, could be written, if the rewind function was used or not, that it's clear for the players. That way, by having more than one scorelist, the point-results remain separate, they don't get mixed up and everything stays fair (because the game is easier with rewinding).
At the top position in each highscore-list would be the player, who used the fewest moves, to complete the levels (the game already tracks move counts). But the scorelist should not show moves, but it could show points. For this, the number of moves could be converted into points, but inversely of course, so that fewer moves result in more points and the player with the most points, stays on top. Each scorelist could, for example, show the best 10 scores so far. If a player uses the "select level" function in the game-menue and doesn't start from the first level, his score shouldn't be included in the scorelists at all. That would naturally skew the results, because the same conditions must apply to all scores in the list, of course. Alot of games use highscore-lists on the C64 and some games also use different scorelists, often depending on the difficulty-level, you've set in the game-menu, or sometimes it also depends on other factors, like the game-speed or something else, it always depends on the specific game, what settings are available. And that multiple scorelist thing works very well, if you ask me, because it guarantees fairness.
This suggestion with the two scorelists, could maybe also be used for your idea with the stars (instead of points). Then the scorelists would show the players with the most stars. In this case, because we have two seperate lists, it would not be necessary, that players, who use the rewind function, receive fewer stars than the others, since the results would be separated in two scorelists anyway.