Parallelizing MapAt

Here is a quick function that does mostly what you want:

parallelMapAt[
   fun_,
   list_List,
   spec__
 ] := Module[{
    copy = list
    },
   copy[[spec]] = ParallelMap[fun, copy[[spec]]];
   copy
  ];

However, the position specification follows the format of Part rather than that of Position:

In[400]:= parallelMapAt[Sin, N @ Range[20], {4, 6, 8, 10}] ===  
  MapAt[Sin, N @ Range[20], List /@ {4, 6, 8, 10}]

Out[400]= True

Another example:

In[425]:= parallelMapAt[f, Array[# &, {5, 2}], All, 2]

Out[425]= {{1, f[1]}, {2, f[2]}, {3, f[3]}, {4, f[4]}, {5, f[5]}}

If you're worried that making a copy of your input is inefficient (frankly, I doubt that it will give you much trouble), you can use SetAttributes[parallelMapAt, HoldAll] and modify the input list itself:

ClearAll[parallelMapAt]
SetAttributes[parallelMapAt, HoldAll]
parallelMapAt[
   fun_,
   list_Symbol?ListQ,
   spec__
   ] := (
   list[[spec]] = ParallelMap[fun, list[[spec]]]
 );

list = N @ Range[20];
parallelMapAt[Sin, list, {4, 6, 8, 10}]
list

Out[420]= {-0.756802, -0.279415, 0.989358, -0.544021}

Out[421]= {1., 2., 3., -0.756802, 5., -0.279415, 7., 0.989358, 9., \ -0.544021, 11., 12., 13., 14., 15., 16., 17., 18., 19., 20.}

Of course, you may want to elaborate the code to do some error checking before you end up ruining your data by Part-assigning corrupt data if the ParallelMap fails.

Edit

As pointed out in the comments, there is still some work to be done since

parallelMapAt[f, Array[h, {2, 3, 4}], All, All, 1] === MapAt[f, Array[h, {2, 3, 4}], {All, All, 1}]

is False. In this case, you'd need to add the levelspec {2} to ParallelMap to make it work correctly. I suspect that the level spec should be equal to the number of non-flattened levels (e.g., All or ;; 3) in spec, but I can't test that right now.