The problem is almost certainly worn separation pad and sub pads. These wear
out at about the same time as the paper pick up roller. All of these can be
replaced but it requires removal of covers and needs a bit of technical
ability. You should replace the Pick up rolleras well as the separation pad and
both sub pads otherwise you will have other feed problems quite quickly.
You can buy the necessary kit, some suppliers provide full instructions or
videos on the replacement procedure. If you are in the USA look at
http://www.fixyourownprinter.com/kits/hp/K30 if not in the USA you should be
able to find a supplier in your geography.
If you are not happy to strip the covers off then I guess it is repair shop
time, you should not pay for more than about 30 minutes labour plus parts.