Natural Magice and more?

[Synchysi]

I thought of replacing them, but then one of them would lose there natural magic as well, correct?

Correct.

so depending on his magic power and level, Shocks damage will be higher or lower.

Right. Shock is just like any other attack. There's absolutely nothing special about it other than it activating from a character's command window.

Whats considered a high natural battle power. I think Gau starts at 99, and believe hes the highest to start.

The cap is 255, so what you consider high may be what you're aiming for in the endgame. The good news here is that level plays a rather sizable role in the physical damage formula, so you'll scale reasonably well regardless.

To find your sweet spot, you will need to experiment. 200 battle power is high, but that may cause that character's damage to get out of control early on in the game. Alternatively, 100 may be good for the early game but he'll likely fall behind later on.