Two main approaches.
1) Edit the sprite itself. Depending what mode you are in you may have a bunch of empty slots in the palette (or things you can possibly crush down). Change the sprite itself to refer to these once blank or now redundant colours and alter the colours within the palette itself if necessary. Assuming you have the space within the palette this should dodge most of the memory issues.
2) Repoint. At some point the game will figure out to load the palette into the palette section. Find this read and point it somewhere else, might have to repeat for the things that ordinarily use that palette. Sometimes it will be calculated, other times it will be of the form 08?????? (or one of the mirrors possibly) directly in the ROM somewhere*.
*not going to even say it is likely to work but as it is a fairly quick thing you might as well. Find the palette in the ROM (dump it from RAM and search the ROM for it, or a fragment of it). If you know where it is in the ROM you can then search for that as a pointer (most GBA games tend to operate with the 08000000 through 09FFFFFF region, which in practice means 08000000 through 08FFFFFF as most ROMs are below 16 megs, hence the GBA pointers always start with 08 line you might have heard, even if it is technically wrong) and maybe change that (or figure out which pointer might be your one if there are multiple) and go from there. If you are going to have to do assembly style tracing to find how the pointer gets created/read then the first part might still save you some time rather than watching it first get loaded into palette memory and going from there.