|"Will the phone repairs get it done..."|
The $49 fee is probably just the minimum charge you pay for just asking them questions about what you should do - it will probably cost you a lot more for labour plus parts for them to come to you, if they even have someone locally that can do that for them, and replace the fan - $100 an hour or more maybe, minimum charge maybe an hour.
This is not something that requires you ship it to HP.
Any local place that repairs computers and has suitable parts (the heatsink and fan are a standard size) can replace the fan or the fan/heatsink combo for a reasonable fee a lot cheaper and quicker, if you take it to them .
This is not rocket rocket science either.
You could easily do it yourself.
Remove the AC power to your case by unplugging it or turning off a power bar it is contected to before doing anything inside your case. The ATX motherboard is always powered in some places as long as live AC is being supplied to the PS, even when the computer is not running, and merely dropping a screw can short something.
Do you have screwdrivers?
If you do, the fan itself is usually easy to remove - 4 cross (phillips) head screws usually, and you don't have to remove the heatsink if you just replace the fan, or if you get a heatsink/fan combo you don't have to replace the whole combo if the fan will screw into the existing heatsink no problem - if the screw holes are the same distance apart, and the fan is the same depth/thickness, it definately will.
If you're not sure which fan to get, take off the old one and take with you to a place that has lots of computer parts - heatsink/fan combos are more common that separate fans, but both are relatively cheap - you can get either.
Replacing a heatsink/fan combo is more complicated, but as I've said, you don't have to replace the heatsink unless the fan or the fan on a combo won't screw onto your existing heatsink.
If you look in your user manual for your model, which is probably already in the Start menu in the Programs somewhere, how to install or remove the cpu fan/heatsink combo is often in that. If you think you can handle that, you just need to get a heatsink/fan combo. If you don't know which one to get, take the combo off and take it with you to a place that has computer parts.