At least in Portugal it's (almost) always used. I can't recall any time where I heard someone saying just "Paulo vem à festa". Actually this last sentence it's a order being given to Paulo, meaning "Come to the Party", while the sentence you posted means "Paulo is coming to the party". "o" is the article. Like you would say "The cat is in front of me" we would say "O gato está à minha frente", we would also say "O Paulo está à minha frente". It would be the equivalent to saying "(The) Paulo is in front of me".
At least in Portugal try to think you should use the "the" also for person names, "o" if it's male, and "a" if it's female.