Rob
I would recommend just running more, and not worrying about stuff like intervals or hill repeats yet.
From your PB's it's clear that your endurance is an issue, as your 5k PB is much quicker than your other two longer distances, which shows you are slowing down over the longer distances.
Therefore, I would concentrate on gradually increasing the number of runs you do, and once you are upto 4 runs a week, then start to gradually increase the distance of one of the runs upto at least 8-10 miles. Almost all of these runs should be done at an easy relaxed pace...
I suspect that doing this over a period of 3-6 months (there are no quick fixes when it comes to building endurance) would get your 10k and 10m PBs down by much more than doing some intervals, etc, AND it will give you a base to carry on improving from.
The only disclaimer is that I havent yet achieved a sub-40 10k, but am hoping it will come this spring off the back of marathon training. My 5k PB is 19:29, 10k is 40:40, and my 10m is 68:24.
Good luck with it!