Looks fine to me (except some indentation). Doesn't work? why? Well, the problem might be in what you omitted to show:

    # replace search paths with data in hash per key,
    # $oldSearchPaths and %searchPaths are initialized elsewhere
[download]

What is in $oldSearchPaths? Shouldn't this also be a hash, and then

    $fileContent =~ s/\Q$oldSearchPaths{$key}\E/\n$searchPaths{$key}/;
[download]

this would do the job? And why is there a leading \n in the replacement part?
Also, you might want to juse the s and g modifiers for s/// if there are multiple ocurrences of paths in the file you are processing. See perlre and Regexp Quote Like Operators.