Sounds like it could be a bit of a tib post strain. I'd probably go down the usual route, then see someone if it isn't settling in a couple of weeks.
Alright Dave, from my limited knowledge I would agree with GCW, posterior tibialis. This does indeed run and then insert where you describe pain. Do a google search for more info, basically it is a deep calf muscle (i.e. not one of the ones you can see) and is responsible for inversion (rolling foot inwards). This is obvious if you imagine it as a rope down that side of the ankle being "pulled tight" / contracting, it would pull foot sideways and up. It also plays a role in supporting shape of arch and plantarflexion (pointing toes down), along with other muscles / structures.
I happen to know this because I have been getting it a lot recently. Mine is due to my broken ankle, basically the lack of movement causes an un-natural walking gait which when overused puts stress on tendon. With me its from pointing foot outwards, so kneecap is on "inside" of ankle and foot i.e. typical limp. This has effect of both flattening arch and forcefully everting foot as you roll "across" foot rather than along its length, both of which strain post tib tendon. This makes me think it may be time to stop affecting your gangsta limp.
Seriously though, I suppose there's a few options:
a) you have a lack of movement or poor function on that side due to an old ankle injury
b) something to do with your walking boots (maybe you need arch supports)?
c) tightness somewhere else in leg that is causing a poor gait
Helen has similar problems due to c). Apparently a glute muscle is lazy which causes incorrect movement at hip, which has knock-on effects down leg. Post tib problems are also related to illiotobal band problems in that they have a similar mechanism. ITB probs cause a bit of pain in knee typically, do you get that too?
Solution wise, rest does work. Helen had to sack of Cuillin halfway along in tears of agony, 3 days later she was fine. Months later we had a walk in Lakes, fine up to 8 miles then same thing. It is an accumulation of tiny traumas so if you don't go too far you'll be fine once its settled. If you want to solve it then I would recommend seeing a chiropractor or physio who specialise in gait to have a look at you to ensure all your muscles are pulling their weight. Also worth doing a bit of self massage to calf. Mine improved loads after I released a knot on peroneus muscle, which is on outside edge of calf and is responsible for eversion. This being tight was pulling my foot into straining post tib all the time. Investigate your whole calf, like as not you will find a really tender area. Give this a good painful ragging regularly for a few days. You can google for trigger points.