Claro que hoje em dia usamos apenas 32 Bits (milhares de cores e
níveis de transparência), já que 8-Bit é uma coisa que só será usada
por quem trabalha com RpgMaker2000 e 2003, nas comunidades de Rpg Maker e
outras comunidades com MMFusion e algumas vezes com Gamemaker.

Este programa foi o melhor que eu encontrei, pois ele fazer a
conversão em método Batch, assim permitindo a conversão de múltiplos
arquivos (vários arquivos de uma vez).
Notou como as imagens desse tópico abriram rapidamente, elas todas juntas pesavam 378kb, mas após convertê-las ficaram com apenas 120kb.

Tutorial:

Primeiramente baixa o FastStone PhotoResizer.

Aviso: Caso você
não tenha direito administrativo no seu windows para instalar novos
programas aconselho que baixe a versão Portable que é só extrair e abrir
que não pedirá autorização.

Após abrir selecione todos os gráficos que deseje converter e arraste para dentro do FS-PR.
Se você for pouco acostumado com isso de arrastar multiplos arquivos use
o próprio sistema de navegação do FS-PR que fica do lado esquerdo
entrando na partição principal, que é geralmente “Disco Local (C:)” e
indo até a pasta desejada, daí clique sobre cada arquivo desejado e
clique em “Add =>”, se quiser todos da pasta atual que você entrou
clique em “Add All ==>”.

https://rpgmaker.000webhostapp.com/rpgmaker/util/FS-PR1.png

Agora selecione em Output Format a opção PNG:

https://rpgmaker.000webhostapp.com/rpgmaker/util/FS-PR2.png

E seguida clique em “Settings” (Configurar), daí altere em Colors: para 256 e em Compression: para Max, Filter deixe em None e não ative a opção interlaced.
Basicamente ficará assim:

https://rpgmaker.000webhostapp.com/rpgmaker/util/FS-PR.png

Agora a opção “Output Folder” é para definir onde você quer que as
imagens convertidas sejam armazenadas para que depois você as localize
para importar para o seu projeto, para mudar a pasta clique o botão
“Browser”.
Se você retirar a opção ele converterá por cima das originais, que não é algo proibido e até útil (Eu faço assim).
Aviso:
Se estiver usando WindowsVista ou Seven e precisar fazer uma edição
rápida pelo MSPaint (Programa padrão de desenho do Windows) numa imagem
PNG de 256 cores você a tornará 24 ou 32 Bit novamente obrigando você a
reconverter.
Ficará assim:

https://rpgmaker.000webhostapp.com/rpgmaker/util/FS-PR4.png

Daí basta apertar o botão [ > Convert]
Pronto, concluído mesmo.


Confirmação:

Confirmando que as imagens convertidas estão mesmo em 8-Bit, 256 cores.
Vá na pasta das imagens convertidas ou na pasta das originais se elas tiverem sido convertidas por cima delas mesmas.
Clique com o botão direito do mouse sobre uma delas e selecione a opção Propriedades que é a última, aparecerá uma janela semelhante a essa:

https://rpgmaker.000webhostapp.com/rpgmaker/util/FS-PR5.png

Clique em “Detalhes”, na linha Intensidade de Bits deverá estar o número 8, se tiver 24 ou 32 é por que você cometeu algum erro ao converter.

https://rpgmaker.000webhostapp.com/rpgmaker/util/FS-PR6.png

EXTRA:
Não
sei a partir de qual versão, mas é possível converter os arquivos em
lote sem acessar diretamente as pastas e ainda manter a estrutura delas.

Basta ir na pasta do jogo ou projeto desejado, selecionar apenas as pastas que deseja ou todas e adicionar em [Add ==>] ou [Add All ==>]:

FS-PR8.png

Assim quando converter, vá na pasta de saída e note que as pastas mantiveram a estrutura na mesma ordem das originais:

FS-PR8.png