What about your accountants? They should recommend someone, or do it themselves.
If you have 10 employees, it's important to understand how payroll and paye works.
With sofware such as Collsoft, you would be just as quick doing it yourself as sending it out to someone to do. The most time consuming part is getting the information together e.g. hours worked, overtime, sick days etc.
It's a while since I used Collsoft, but at the time, they provided an excellent service and were also very helpful in answering PAYE type questions as well. Ideal for the small business.
Even if you farm it out, I still suggest that you get to understand it, so you can review the work done by the subcontractor.
Brendan