Thanks for your help! I spent a whole night trying to figure out how to put it into practice, but I think I've got it. Let me explain:
First I tried to do exactly what you suggested: Search for matches with the value A9 03 and modify it looking for any change on the sprite.
This, actually only works with the main sprite, and only in one of the matches with the value.
Anyway, when I checked that the palettes were indeed assigned with a value from 00 to 03, I thought: If the rest of sprites work the same, I ONLY have to check all values '03' until I locate the one I want to modify.
A system as you can imagine, horribly slow, but I still found the value I was looking for. Actually, the first sprite I want to modify uses 4 values '03' for each frame.
At this point something happened that disoriented me: I managed to change the sprite's color palette when walking to the left, but the sprite still used the original palette when walking to the right!
I continued trying for hours to modify values '03' without result. After discarding practically any other idea, I investigated further the area where I made the palette modifications... and it turns out that when the sprite walks to the right it uses a '4' in front, instead of a '0'. In other words, the values I couldn't find were in the same place with another name...
At least I managed to modify the first sprite, and I think that repeating it now that I understand better how the values are grouped I will be able to do it faster.
Still, if you can think of how I could improve my searches, I'm all ears