How difficult/costly would it be to extend a 400V 3-phase domestic supply 150m down a garden in the UK?
Compared to solving this problem with a high-current single-phase installation, are there likely to be any extra costs or regulatory hoops to jump through to do it with 3-phase?


No, there will not be any extra regulatory hoops.

As to materials cost a three phase DB will cost more than a single phase one but the cable is likely to work out cheaper. Overall I would expect for a given power level a three phase feed to work out cheaper than a single phase one. 

Don't expect this to be a cheap job, mostly because you are going to need a long peice of fat cable. Using aluminium cable is an option to lower the cable costs but it can be difficult to find electricians who know how to work with it safely.

Any electrican who regually does commercial work will know how to deal with three phase.


  Can we legally terminate it in our timber structure and distribute both 3-phase and single-phase sockets from there?


As long as the structure is sturdy, weathertight  and reasonablly permanent the fact it's timber shouldn't be a problem.


  Do we need to get permission from the power company or any regulators?


The job will be notifiable under "Part P" because new circuits are involved but nearly all electricans will be part of self-certification schemes so that should be a non-issue.