In ptBR, what these interjections mean partially depends on context, facial expression and gesture. Most of the time "um-hum" means "sim" but it can also mean "sei", "concordo", or, if you shake your head and give the right intonation, it can mean "não". So don't put too much trust on the fact that it usually means "yes". We also say "ã-hã" (or hã-hã) and á-há. They usually mean "no", but sometimes "yes", and "a-há" can also be used wben you catch someone red-handed ("a-há", peguei-te em flagrante"). Stress and intonation are 90% of the meaning in such cases. Unfortunately I can't help much using the written language.
As for the first question, when people started replacing "yes" with these interjections, I couldnt find an answer. At a guess, it makes sense to me to assume their use antedated "yes" and they must have been used in primitive societies just like other interjections (oh, ah, ouch, hey)