Very nice post LillSophie. I would like to add that red staining and skin can also be a result of the licking solely. It is when it is combined with the other symptoms you mentioned (reddish build up between toes and discolored nail at the cuticle) that it is from the yeast infection.
The ultimate etiology should be dealt with, but you can do a simple foot bath to treat the fungus.
Some dog do lick to the point of self-mutilation.
One thing not mentioned is nervous system issues. Some dogs, like humans develop disc and vertebral issues. Spondylosis (arthritic changes of the vertebrae) can pinch different nerves. Common symptoms for brachial plexus pressure is obsessive front paw licking. I know a Doberman who has this issue. An intuitive owner saw his behavior changes in his work and his new paw licking habit and contacted a Vet. Now with NSAIDs and regular adjustments, he is fine.