You might want to do a bit more research on bit-depths of PocketPC devices before writing an 8-bit engine. The large majority of current devices (if not all) have 16-bit frame-buffers/displays, or at least 16-bit pixel formats that the hardware display chops down to get what it needs.
Also bear in mind that on a machine with a non-performant memory bus, 256-colour palette matching (and lookups) are probably slower than working in 16-bit and using "proper" 5.6.5 colour intensities.
To sum up:
use 16-bit.
(I'm not talking specifically about PocketFrog here - I don't know much about it).