You should be able to make all the city symbols in the left column with simple Photoshop brushes. Check to see what brushes you have already and if you need other ones (like stars or squares) do a search for free Photoshop brushes. You should be able to find some.
Also remember that you can make a brush in Photoshop. So for instance you could make nearly any customs shape and turn it into a brush.
Another possibility is to search through free font sites and check out their symbol or "dingbat" fonts which are mainly symbols.
Finally, instead of a brush, think about using a symbol on a separate layer as a master, duplicate it, and move it to where you want it. Then you can make the master layer invisible.