(1) take basis address pc: 06/B359
(2) check in Hyrule Magic the sprite number you want to change; Blue soldier is 41

(3) add this in HEX! to 06/B359:
06B359+41=06/B39A
(4) at pc 06/b39a you find the 19 which is blue for blue soldier. Change the palette according to the palette key below to your wishes (e.g., 19 is blue palette, 17 is red, 1b is green.
.

This works for every sprite so you can edit the palette specific to each sprite now! An exception are stage 2 sprites that change forms, like the amos statues. See below how to change them.


Here's the palette key:


Here's when you change at 06/B39A the 19 to 1d (all blue soldiers changed to golden):


In case you need another color in the global palette you need to repixel each gfx.


Stage 2 sprites:
Some sprites change forms, so you need to change the palette a second time.
crab giving rupees when lifted bush:  03/2915: 09
amos when awoke: 02/B759: 0b
blue tektite 03/0D8E: 09
red tektite 03/0D8f: 07  
leevers: 03/0dea:02

The key is similar to above palette key, only that you need to substract 10 (e.g., blue is 09 instead of 19, red is 07 instead 17). You may notice that amos when awake is actually the green palette (0b or 1b). The code rewrites the green palette so that awoke amos statues look golden. So you cannot have green sprites (like green soldiers together with the amos statues in one screen.