Can you replace "lhe" with "o" here?
Is there a guide/rule about using lhe/o/ a ele ?
The direct object "o" is used with transitive verbs while "lhe" and "a ele" are indirect objects.
I saw him. = Eu o vi.
I told him = Eu lhe disse./ Eu disse para ele.
I have already told him many times.
You tell someone something
You say something to someone.
"I have already told..." or "I already have told..." mean the same in English; furthermore, the order of the words in the sentence is "Eu já lhe disse..." So what are we translating here - the concept or the word for word meanings?
The placement of adverbs of frequency in Portuguese is irrelevant when translating to English.
O advérbio de frequencia normalmente se coloca entre o verbo auxiliar e o verbo principal.
I have already told him.
When we speak informally in AmE, we very often use the simple past with the adverbs "just", "already", and "yet". It's an "allowed exception" and is one of the principal differences in grammar between BrE and AmE.
A discussion of different uses of present perfect in AmE and BrE: