Valery, there is fastest way, it is called "actions" in photoshop.
1. Take all images, that color palette must be changed (all frames of one unit) in one separate folder.
2. Create one more folder, call it "indexed color", for example.
3. Open photoshop
4. Open one frame in photoshop
5. (!) go to action tools (window->actions), pick on "create new action" button (bottom of actions window); name the created action "changing palette", for example. Now all editing that you do - photoshop records.
6. Change palette to your opened frame from RGB to indexed palette, that you already have (!).
7. Save frame without changing name in folder "indexed color" (or any other name, that you did)
8. Close the frame.
9. (!) Stop record (at bottom of action window button "stop")
10. Go to "File -> Automate -> Batch". In batch window set action, that you did (in our case - "changing palette"); in "source" field click "choose" button and choose folder where is all frames (see step 1); click "ok".
11. Take sprite and popcorn, sit сonveniently and watch how the photoshop do your job .
12. Go to folder "indexed color" (see step 2) and take all your frames in indexed color format.

P.S. if you have any problem - ask here; when I have time, I answer .