We have used a company just outside Cambridge who I can recommend - dB Technology. They are geared up for both precompliance work and actual compliance work. Their sfotware seems to be mostly home grown and the engineers there (hi Stephen) are highly knowledgeable and have seen pretty much every problem there is. Also might be work talking to Unit3 Compliance, I know the owner and went to one of his training courses recently and he has a wealth of knowledge. He's usually quite busy though so it could be several months before you get to be seen, I guess that's a good sign.
In general, expect to pay around £500 per half day - some test houses require a full day's booking. So a realistic budget for precompliance is probably £1-2k if there are no major headaches to be solved. Then actual compliance could be a fair bit more, maybe £3-5k.
The majority of precompliance work can be done in a half day session I dare say - arrive exactly on time to maximise your booking. It helps to have a lab that's not afraid of running a "quick sweep" to identify problem areas. Usually that will consist of using a higher RBW than the standard specifies which sacrifices accuracy for speed. Then when you have identified problem areas you do a proper test at the rated RBW.
Do be aware you do not technically have to perform an EMC test to be CE marked (in most device classes.) So you may be able to focus on just the intentional radiator parts for your test. You can do a technical assessment and justify that based on circumstances X/Y/Z (like using good design practices, well shielded case, etc.) the product is likely to comply with the rest of the standard. However, if you do get called up on that, you will have to prove to a legal standard that the product was compliant. Doing the tests gives you a presumption of compliance which is highly advantageous should Ofcom or Trading Standards, or an EU body, wants to review your technical file.