Kllrnohj's always like that ^^ even to Kerm sometimes
I wouldn't be surprised if the code you need is only a couple of lines. Like you said, you probably need to load in a new pallete into the sprite and bg pallete memory. This may only take a couple lines of code.
however:
1.) do you have a way to load this onto your gba cartridge? iirc, it's generally flash locked or something iirc.
2.) do you have the source? even if you disassemble, all you get is a bunch of garbage hex numbers w/ no discernable meaning. Considering how complex ARM ASM is, this can be more difficult than brandonw disassembling the ti83+'s flash.
3.) is it worth the effort? Like Kllrnohj pointed out, it's illegal to modify that game. but also, if you knew how to do it, why would you? you'd probably be some 1337 coder who could code gba and nds games. You wouldn't need to play pokemon anymore, you could make your own franchise and become a licensed Nintendo developer and make $$!!! lol <- btw, this mean "L-O-L", the forums auto catch "L-O-L" and replace it with lol ^^
but like I said before, I have no clue how to do this, and I doubt anyone here would know because this is a forum for z80 Assembly, and more specifically for TI graphing calculators.
you should try
http://forum.gbadev.org/ or some other gba dev forum. There you will probably find gurus in developing for both the gba and nds in C/C++ and ARM ASM.