Hello Feebs,
The first syllable of Paulo (Pau.lo), is a diphthong similar to "foul", the second, though unstressed, is clearly pronounced as the poetical interjection "Lo!". Coelho, has thress syllables (Co.e.lho), all the vowels are distincly pronounced, but the stress falls on the "e", which sounds like the first "e in "leverage". In the first syllable you have a lateral approximant of a liquid like "l" and "r" (the lambda of the IPA alphabet), is it difficult to describe how the sound is produced, but it aproximates to "ljo", where the "j" is a semivowel in the same way as in new /njew/.