OK, so the plan is to change the cave's 'S' save point back to the original campfire one. Since I would have to gather the data myself at some point anyway, I'll just do that conversion and document the process.
First, let's see what changes Square made. I saved the game at the campfire save point in the Watery Pass and then loaded that save with both versions of the game. I use the bsnes debugger because of its neat Palette Viewer:

As you can see, there is no difference between the versions, so they didn't alter the palettes but simply associated the tiles with another one.
Next we go where we always go first when we need to locate something in the ROM: To Yousei's FFIV hacking document!

Here we find this:
A2000-A5FFF (149E00-14DDFF) Town Map Tile Formation Data (*4)
*4 -- Town Map Tile Formation Data, 2 bytes
0x0000 8x8 tile (0x00-0xFF)
0x0001:0...1 ?
0x0001:2-4 Palette Index
0x0001:5 Tile Priority (0 = behind character, 1 = in front of character)
0x0001:6 Flip tile horizontally
0x0001:7 Flip tile vertically
What Yousei identified as "Town Map Tile Formation Data" actually contains formation data for all locations! I always work with unheadered ROMs, so I converted his data and broke it down to this:
A1E00-A5DFF (149E00-14DDFF) Location Map Tile Formation Data
A1E00-A21FF (149E00-14A1FF) Airship
A2200-A25FF (14A200-14A5FF) Lunar Core
A2600-A29FF (14A600-14A9FF) Cave Magnes/Sealed Cave
A2A00-A2DFF (14AA00-14ADFF) Castle Exterior
A2E00-A31FF (14AE00-14B1FF) Town Exterior
A3200-A35FF (14B200-14B5FF) Town Interior
A3600-A39FF (14B600-14B9FF) Castle Interior
A3A00-A3DFF (14BA00-14BDFF) Crystal Room
A3E00-A41FF (14BE00-14C1FF) Tower (Save Room)/Big Whale
A4200-A45FF (14C200-14C5FF) Sylvan Cave/Land of Monsters
A4600-A49FF (14C600-14C9FF) Tower
A4A00-A4DFF (14CA00-14CDFF) Giant
A4E00-A51FF (14CE00-14D1FF) Lunar Subterrane
A5200-A55FF (14D200-14D5FF) Mountain
A5600-A59FF (14D600-14D9FF) Cave
A5A00-A5DFF (14DA00-14DDFF) Ship
What this "Tile Formation Data" does is take the individual tilesets in the ROM...

(left:US, right:Japanese)
and arrange them into 16x16 pixel "building blocks" that the game will then construct the maps from:

Now the fun part! Let's take a look at the Tile Formation Data for the Cave.
Japanese version:
43 0C 8A 04 1F 04 86 04 81 04 81 04 92 04 1C 04 20 04 22 04 22 04 83 04 0E 04 01 04 93 44 24 11
40 04 42 04 42 04 83 04 01 04 01 04 01 04 4E 04 90 04 A4 04 91 44 D0 04 D2 04 D4 04 00 04 6A 04
B0 04 8A 04 8A 04 23 0D 20 0D 00 04 00 04 4A 04 B6 04 B8 04 BA 04 97 44 96 44 9B 04 8A 04 01 04
D6 04 D8 04 DA 04 76 04 25 04 14 04 8A 04 8A 04 06 04 02 04 04 04 8A 04 8A 04 99 44 98 44 5E 44
84 04 37 08 82 08 57 48 58 08 59 48 39 08 60 04 01 04 60 04 01 04 01 04 72 04 74 44 8A 04 8A 04
9C 24 83 24 01 24 01 24 92 04 94 04 93 44 94 04 2E 04 90 04 91 44 9C 24 9C 24 21 0D 99 44 98 44
BE 04 B8 04 BA 04 B0 04 9E 04 BA 04 8A 04 EC 18 01 24 A4 04 DC 04 BA 04 23 34 00 04 01 04 7C 04
78 04 78 04 3C 04 2A 04 DE 04 D8 04 DA 04 F0 1C F2 1C 23 0D 3C 04 2A 04 9B 04 8A 04 3E 04 F6 18
44 0C 8B 04 49 04 81 04 81 04 86 44 93 04 1D 04 21 04 6B 04 20 44 01 04 8B 04 83 44 92 44 6B 04
41 04 6D 04 40 44 01 04 01 04 83 44 5E 04 4F 04 91 04 A5 04 90 44 D1 04 D3 04 D5 04 00 04 6D 04
8B 04 8B 04 B5 04 23 0D 20 0D 96 04 97 04 4B 04 B7 04 B9 04 BB 04 00 04 00 04 8B 04 9B 44 01 04
D7 04 D9 04 DB 04 77 04 26 04 15 04 8B 04 8B 04 06 04 03 04 05 04 98 04 99 04 8B 04 8B 04 01 04
85 04 38 08 57 08 82 48 59 08 58 48 0F 08 61 04 01 04 61 04 01 04 74 04 73 04 01 04 98 04 99 04
9C 24 01 24 01 24 83 64 93 04 95 04 92 44 95 04 2F 04 91 04 90 44 9C 24 9C 24 21 0D 8B 04 8B 04
B7 04 B9 04 BF 04 8B 04 B7 04 9F 04 B5 04 ED 18 83 64 A5 04 B7 04 DD 04 24 34 00 04 01 04 7D 04
79 04 79 04 3D 04 2B 04 D7 04 D9 04 DF 04 F1 1C F3 1C 23 0D 3D 04 2B 04 8B 04 9B 44 3F 04 F7 18
45 0C 8C 04 1F 04 83 04 01 04 01 04 A2 04 2C 04 30 04 32 04 32 04 83 04 0C 04 01 04 8C 04 25 11
50 04 52 04 52 04 10 04 12 04 12 04 01 04 8C 04 A0 04 8C 04 8C 04 00 04 B2 04 B4 04 00 04 52 04
9D 04 C2 04 C4 04 23 0D 22 09 00 04 00 04 5A 04 C6 04 C8 04 CA 04 A7 44 A6 44 AB 04 8C 04 88 04
E6 04 E8 04 EA 04 8E 04 29 04 16 04 8C 04 8C 04 0B 04 07 04 09 04 8C 04 8C 04 A9 44 A8 44 01 04
18 04 47 08 66 08 67 48 68 08 69 48 35 08 70 04 01 04 62 04 1A 44 01 04 64 04 75 44 8C 04 8C 04
01 24 83 24 01 24 01 24 A2 04 8C 04 8C 04 8C 04 A1 04 A0 04 8C 04 01 24 01 24 00 04 A9 44 A8 44
CE 04 BD 04 CD 04 9D 04 AE 04 CA 04 C4 04 EE 18 01 24 8C 04 6F 04 CA 04 33 34 00 04 01 04 7E 04
7A 04 7A 04 4C 04 3A 04 E0 04 E2 04 E4 04 F4 1C F4 1C 23 0D 4C 04 3A 04 AB 04 8C 04 5C 04 F8 18
46 0C 8D 04 49 04 01 04 01 04 83 44 8D 04 2D 04 31 04 6C 04 30 44 01 04 8D 04 83 44 A2 44 6C 04
51 04 6E 04 50 44 11 04 11 04 10 44 01 04 8D 04 8D 04 8D 04 A0 44 B1 04 B3 04 00 04 00 04 6E 04
C1 04 C3 04 AD 04 23 0D 22 09 A6 04 A7 04 5B 04 C7 04 C9 04 CB 04 00 04 00 04 8D 04 AB 44 89 04
E7 04 E9 04 EB 04 8F 04 13 04 17 04 8D 04 8D 04 0B 04 08 04 0A 04 A8 04 A9 04 8D 04 8D 04 01 04
19 04 48 08 67 08 66 48 69 08 68 48 36 08 71 04 1A 04 63 04 01 04 75 04 65 04 01 04 A8 04 A9 04
01 24 01 24 01 24 83 64 8D 04 8D 04 A2 44 8D 04 A3 04 8D 04 A0 44 01 24 01 24 00 04 8D 04 8D 04
BC 04 CC 04 CF 04 C1 04 C7 04 AF 04 AD 04 EF 18 83 64 8D 04 C7 04 7F 04 34 34 00 04 01 04 80 04
7B 04 7B 04 4D 04 3B 04 E1 04 E3 04 E5 04 F5 1C F5 1C 23 0D 4D 04 3B 04 8D 04 AB 44 5D 04 F9 18
US version:
43 0C 8A 04 1F 04 86 04 81 04 81 04 92 04 1C 04 20 04 22 04 22 04 83 04 0E 04 01 04 93 44 24 11
40 04 42 04 42 04 83 04 01 04 01 04 01 04 4E 04 90 04 A4 04 91 44 D0 04 D2 04 D4 04 00 04 6A 04
B0 04 8A 04 8A 04 23 0D 20 0D 00 04 00 04 4A 04 B6 04 B8 04 BA 04 97 44 96 44 9B 04 8A 04 01 04
D6 04 D8 04 DA 04 76 04 25 04 14 04 8A 04 8A 04 06 04 02 04 04 04 8A 04 8A 04 99 44 98 44 5E 44
84 04 37 08 82 08 57 48 58 08 59 48 39 08 60 04 01 04 60 04 01 04 01 04 72 04 74 44 8A 04 8A 04
9C 24 83 28 01 28 01 28 92 04 94 04 93 44 94 04 2E 04 90 04 91 44 9C 28 9C 24 21 0D 99 44 98 44
BE 04 B8 04 BA 04 B0 04 9E 04 BA 04 8A 04 EC 18 01 24 A4 04 DC 04 BA 04 23 34 00 04 01 04 7C 04
78 04 78 04 3C 04 2A 04 DE 04 D8 04 DA 04 F0 1C F2 1C 23 0D 3C 04 2A 04 9B 04 8A 04 3E 04 F6 1C
44 0C 8B 04 49 04 81 04 81 04 86 44 93 04 1D 04 21 04 6B 04 20 44 01 04 8B 04 83 44 92 44 6B 04
41 04 6D 04 40 44 01 04 01 04 83 44 5E 04 4F 04 91 04 A5 04 90 44 D1 04 D3 04 D5 04 00 04 6D 04
8B 04 8B 04 B5 04 23 0D 20 0D 96 04 97 04 4B 04 B7 04 B9 04 BB 04 00 04 00 04 8B 04 9B 44 01 04
D7 04 D9 04 DB 04 77 04 26 04 15 04 8B 04 8B 04 06 04 03 04 05 04 98 04 99 04 8B 04 8B 04 01 04
85 04 38 08 57 08 82 48 59 08 58 48 0F 08 61 04 01 04 61 04 01 04 74 04 73 04 01 04 98 04 99 04
9C 24 01 28 01 28 83 68 93 04 95 04 92 44 95 04 2F 04 91 04 90 44 9C 28 9C 24 21 0D 8B 04 8B 04
B7 04 B9 04 BF 04 8B 04 B7 04 9F 04 B5 04 ED 18 83 64 A5 04 B7 04 DD 04 24 34 00 04 01 04 7D 04
79 04 79 04 3D 04 2B 04 D7 04 D9 04 DF 04 F1 1C F3 1C 23 0D 3D 04 2B 04 8B 04 9B 44 3F 04 F7 1C
45 0C 8C 04 1F 04 83 04 01 04 01 04 A2 04 2C 04 30 04 32 04 32 04 83 04 0C 04 01 04 8C 04 25 11
50 04 52 04 52 04 10 04 12 04 12 04 01 04 8C 04 A0 04 8C 04 8C 04 00 04 B2 04 B4 04 00 04 52 04
9D 04 C2 04 C4 04 23 0D 22 09 00 04 00 04 5A 04 C6 04 C8 04 CA 04 A7 44 A6 44 AB 04 8C 04 88 04
E6 04 E8 04 EA 04 8E 04 29 04 16 04 8C 04 8C 04 0B 04 07 04 09 04 8C 04 8C 04 A9 44 A8 44 01 04
18 04 47 08 66 08 67 48 68 08 69 48 35 08 70 04 01 04 62 04 1A 44 01 04 64 04 75 44 8C 04 8C 04
01 24 83 28 01 28 01 28 A2 04 8C 04 8C 04 8C 04 A1 04 A0 04 8C 04 01 28 01 24 00 04 A9 44 A8 44
CE 04 BD 04 CD 04 9D 04 AE 04 CA 04 C4 04 EE 18 01 24 8C 04 6F 04 CA 04 33 34 00 04 01 04 7E 04
7A 04 7A 04 4C 04 3A 04 E0 04 E2 04 E4 04 F4 1C F4 1C 23 0D 4C 04 3A 04 AB 04 8C 04 5C 04 F8 1C
46 0C 8D 04 49 04 01 04 01 04 83 44 8D 04 2D 04 31 04 6C 04 30 44 01 04 8D 04 83 44 A2 44 6C 04
51 04 6E 04 50 44 11 04 11 04 10 44 01 04 8D 04 8D 04 8D 04 A0 44 B1 04 B3 04 00 04 00 04 6E 04
C1 04 C3 04 AD 04 23 0D 22 09 A6 04 A7 04 5B 04 C7 04 C9 04 CB 04 00 04 00 04 8D 04 AB 44 89 04
E7 04 E9 04 EB 04 8F 04 13 04 17 04 8D 04 8D 04 0B 04 08 04 0A 04 A8 04 A9 04 8D 04 8D 04 01 04
19 04 48 08 67 08 66 48 69 08 68 48 36 08 71 04 1A 04 63 04 01 04 75 04 65 04 01 04 A8 04 A9 04
01 24 01 28 01 28 83 68 8D 04 8D 04 A2 44 8D 04 A3 04 8D 04 A0 44 01 28 01 24 00 04 8D 04 8D 04
BC 04 CC 04 CF 04 C1 04 C7 04 AF 04 AD 04 EF 18 83 64 8D 04 C7 04 7F 04 34 34 00 04 01 04 80 04
7B 04 7B 04 4D 04 3B 04 E1 04 E3 04 E5 04 F5 1C F5 1C 23 0D 4D 04 3B 04 8D 04 AB 44 5D 04 F9 1C
These are basically hex representations of the "building blocks" pic above. Each 8x8 tile is represented by 2 bytes. The first byte is the value of the tile itself (in the original tileset), the second one holds three properties at once: palette association, tile priority and horizontal/vertical flipping (see the bit from Yousei's document above).
I get confused very easily when working on the binary level as described by Yousei, therefore I went ahead and wrote down all the possible combinations one might encounter in the second byte:
04,08,0C,10,14,18,1C Palette 1-7 behind character
24,28,2C,30,34,38,3C Palette 1-7 in front of character
44,48,4C,50,54,58,5C Palette 1-7 behind character, horizontally flipped
64,68,6C,70,74,78,7C Palette 1-7 in front of character, horizontally flipped
84,88,8C,90,94,98,9C Palette 1-7 behind character, vertically flipped
A4,A8,AC,B0,B4,B8,BC Palette 1-7 in front of character, vertically flipped
C4,C8,CC,D0,D4,D8,DC Palette 1-7 behind character, h&v flipped
E4,E8,EC,F0,F4,F8,FC Palette 1-7 in front of character, h&v flipped
If all you want is to change a tile's palette, locate its 2nd byte number in the table above and change it to one in the same line.
There is one additional twist to the hex data above: It is arranged in the following way: All upper left tiles first, then upper right, lower left, and finally all lower right tiles. (Anything else would have been too easy!)
Let's just do the campfire and see if we know what we did afterwards...
The tiles (in both versions) are F6, F7, F8, F9. If you look at the "building block" pic you'll see that the save point graphic is the very last in the lower right corner, which is great! We should therefore find it right at the very end of our hex data. And there it is. "F9 18" (Palette 6, behind character) in the Japanese version and "F9 1C" (Palette 7, behind character) in the US version.
So where are F6, F7, F8? Right at the end of their own segments! I think a picture can't hurt here for clarity:

All that's necessary now is to restore these four values and copy over the original graphics (you could also just copy and paste the entire thing, but that would also undo the palette changes they made to make secret passages more obvious).
It's kinda late here and I hope I'm making sense... If anyone has suggestions to make things clearer or more precise, please tell me! And feel free to ask anything.
Regards!