Whilst it is not recommended as a regular driving technique, I find with new shoes raising the handbrake lever whilst the vehicle is moving slowly is helpful in bedding them in and taking the high spots off. If you're changing the shoes it's probably about time to change the cable too, as a new one can give you a crisper, tighter feel. Don't forget, you can adjust the cable too, at the lever end. Some of those five clicks are probably just taking up slack in the cable.