When we use "an air of X" in describing a person's (or dog's!) behaviour, we are talking about that person's manner or attitude. As Oksana said, a footpad is a robber or bandit who would follow his victims quietly before attacking them. "...the little dark-brown dog who was following him the way a bandit would quietly follow his victim."

Footpad (archaic) means a robber or highwayman, on foot rather than horseback So, this sentence could be interpreted as... the dog was following him and looked threatening

A foot pad is a foot stool for resting the feet, so in this sentence the dog was so devoted that he was willing for the person to even rest his feet on him.