>When I export the image (after adding a layer) to .ICO format, Gimp show the following Icon Details:
>1. 4 bpp, 1-bit alpha, 16-color palette (since this looks larger this must be the initial 32x32 layer)
>2. 8 bpp, 1-bit alpha, 256-color palette (new layer).
>
>Should I change the 2nd layer to 16-color palette too?

The smaller icons were invented when graphics were lower grade, so for them 16 colors is tolerated. However, for the newer, larger formats, you should use more colors, as that's what's expected of that standard. Perhaps you should do them all in 256 colors or 32 bpp - it's actually hard to find a video card still in use which can't. The one I finally dumped this month was twelve years old and it had 32 bpp color capability. So go for the richest standard wherever you can.