Why can't it be 'I agree with them completely'?
It certainly can be "I agree with them completely." In English the position of the adverb is variable. The form makes it clear that it modifies the verb. Be careful, though, moving the adverb around can change the emphasis.
hoàn toàn đồng ý = 完全同意
"I agree with them completely" does not change the meaning and it is more fluent English.