Try the brake pad replacement but first of all i would always fit new shimano inners and outers and make sure theres no kinks at all. A few drops of rock & roll cable oil if you have it and see how you get on.
*Its scotland. Cable oil even in new shimano cables is always a good thing!
Going by how much of a difference new quality cables make to all cable operated brakes,i would try this before buying any brake pads. Check the old pads to see if anything has lodged its way into the rubber but you will probably find the best upgrade being fresh quality cables.

