The 'increase magical damage' formula is an enchantment. You need to find the enchanter in order to add or remove enchantments on equipment which have enchantment slots. Before getting the battle tower there is an enchanter to the far west of Lovis' tower, and then north a bit.
Talking to the tree, only potion formula will be listed, not enchantment formula.
You can add charms either from the equipment list, or the inventory. The equipment must have an empty charm slot (charm and equipment slots are separate, though higher level equipment tends to have both; earlier in the game charm slots will start showing up before enchantment slots).
