Where is the StarCraft color pallete? I can't seem to find it.

For the menus, it is the palette for glue\pal*\backgnd.pcx (or whichever background pcx file is used for each menu). In-game it is tileset\*.wpe (where * is the tileset).

There are a number of them...

For a given tileset, the units&sprites (excluding the player-based-color parts) and the terrain will use the same palette (.WPE) file, the first 5 tilesets are in StarDat.mpq, you will need to add a listfile to see them, in the archive it's called "ListFile.txt"

"tileset\badlands.wpe"
"tileset\platform.wpe"
"tileset\install.wpe"
"tileset\ashworld.wpe"
"tileset\jungle.wpe"

The next three are in BrooDat.mpq, no extra listfile should be required

"tileset\Desert.wpe"
"tileset\Ice.wpe"
"tileset\Twilight.wpe"

Then there are player minimap colors, which you'll find in "StarDat.mpq\game\tminimap.pcx"
And player colors used to color units/sprites, which you'll find in "StarDat.mpq\tunit.pcx"

There are many others, but i've yet to use more than these.

Do note that the pcx ones still refer to the wpe master palette in-game, they are just reindexing tables so certain palette indices will be remapped to others.
If you want to know all of the pcx color tables, it's pretty much any that start with the letter 't' (tunit, tfont, twire ... for in-game only, they are game\*.pcx) and the transparency tables in terrain\*\*.pcx.

what about icon palette ?

Oh, sorry, I forgot that one was in a different place. unit\cmdbtns\ticon.pcx