Paint.NET :: Matching Top Layer To Bottom One

I have a photo of two guys as the background, and two more layers on top to put a ZZ Top beard on each of them.  I cut out the beard from a Billy Gibbons photo, and trimmed it up as good as I can.  In the Billy picture he is wearing a black shirt, so behind the reddish beard are traces of black.
 
The issue:The first guy in the background is also wearing a black shirt, so the beard blends perfectly on him.  However, the second guy is wearing a turquoise shirt, and as a result, the beard does not blend well whatsoever, and the edges are terrible.  I need a method to color change (or whatever) so that the black traces on the beard become turquoise traces, and thus blend with his shirt. 
 
I don't want to solve this with some kind of feathering or blur, because I want the edges of the red beard to be sharp, like they look on the first guy.  I think I need to solve this with a color changing technique, but now sure how to do it in Paint.net.
 
Although I'm relatively new with Paint.net, years ago I became quite proficient with PaintShop Pro doing web applications.  As I recall, there was a function of the color changer there, which would not only change from Color 1 to Color 2, but would preserve the differences in the color shades.  So far example, if you set the color changer to change a blue shade to a red shade, and set the tolerance up some, not only would it include several blue shades from the source, but it produce various shades of red in the destination.  So the result was not just a solid spot of red, but rather a nicely shaded red,
 
I have looked at the Paint.net color changer, and although I see how the tolerance level can dictate various shades of input to include, it seems to map all of those included pixels to just plain red, one exact color.  I'm thinking surely it will do what I want, but for the life of me, I can't find it in the tool or in my searches.