Can you check the motherboard model again? It looks like a MSI model number, but they don't list A58M-E35. My guess is A55M-E35 or else A78M-E35.
In any case, the upgrade options are limited, both in terms of number of possible APUs and in terms of additional performance gained for the cost. Here would be the options if you have A78M-E35, with current APU at the top for comparison:
A8-6600K is 3.9 GHz base / 4.2 GHz turbo / DDR3-1866 / intGPU 256 graphics cores @844 MHz =HD8570D
A10-6800K is 4.1 GHz base / 4.4 GHz turbo / DDR3-2133 / intGPU 384 graphics cores @844 MHz =HD8670D
A8-7650K is 3.3 GHz base / 3.8 GHz turbo / DDR3-2133 / intGPU 384 graphics cores @720 MHz =R7-6CU
A10-7850K is 3.7 GHz base / 4.0 GHz turbo / DDR3-2133 / intGPU 512 graphics cores @720 MHz =R7-8CU
So there are a few options, but if you can afford Ryzen, the Ryzen 3 2200G is a good value.
