If the private key is represented in hex and n characters are mutated then there are 64! * 15 n / (64 - n)! possibilities to search through.
The attacker knowing the address (or even the full public key) doesn't tell him anything beyond giving him a way to know if a private key guess is correct or incorrect.
Assume a hardcore attacker (one e.g. with a repurposed GPU mining rig) can test 14e9 keys for 1 USD, then here are the attack costs:
mutations possibilities cost to crack
-----------------------------------------
1 960 ~0
2 907e3 ~0
3 844e6 0.06 USD
4 772e9 55.14 USD
5 695e12 49652.86 USD
As you can see, changing at least 5 digits in totally random locations makes an attack prohibitively expensive. However, most humans will make less than totally random choices about which characters to mutate ... e.g. if I were attacking someone who I suspected of using the scheme you described I would assume they would be more likely to mutate successive digits ... especially at the very beginning or end. E.g. if I knew for sure only the last 8 digits were mutated it would only cost 0.19 USD to check.