(After)having completed his work, he left his office. Is there any difference in meaning between with and without 'After' in the sentence
There is perhaps a slight difference in nuance.
"Having completed his work, he left the office", suggests that the work completion was necessary, in order that he might leave.
However "After having completed his work, he left the office", does not suggest as strong a connection between the two events. At least that is the way the senses of the two sentences differ to my (UK) ear. But it is a very fine distinction and I would be interested to hear other opinions.
The descriptor After is generally considered a notation of time. "After having" is a bit redundant in that specific sentence, and would generally be considered unnecessary considering the context. Usage with the word after would likely be, "After completing his work, he left his office."
If you choose to use "After" in the sentence, it generally implies there were other things that the subject in question had to consider before his work was able to be completed. So while there is a difference, it is a very slight one.