Signs could definitely work. Maybe a sign with a little arrow on it?
About the color palette. This is what I do; Just rip it from another sprite. That's all you really have to do. Put some tiles together and see if they compliment each other and then recolor recolor recolor. Each sprite can only have a max of three colors if it's a tile and two if it's a sprite. The only exception is if the sprite has something special about it. [i.e. a red bow or holding an item.] If there is something special about it, still keep that to two color so you should have a max of three colors on a sprite. Let's say you had a girl with a bow. She would have a white color for her skin and yellow for the dress and the shadows on her face. The bow would be red and use white again for the highlight. Now, tiles could be a little different. It depends on how strict to GB style you want to be. In my more recent pieces, I break the rule of three colors because I make tiles that are like transitional tiles between two areas. So it would have a bit of each tile on either side of it thus making it have five or six colors. If you don't want to do that and you want to keep it traditional, then just stick to the rule of three colors. Sooo, to sum up the overly long post about color palette, rip your colors from other sprites, stick to a maximum of three colors per tile and make sure all the tiles in the area compliment each other in terms of color theory. Hope that helps a bit?