"He comes on Monday at the latest."
Translation:Er kommt spätestens am Montag.
I have heard that usage with time "gegen dreizehn Uhr" meaning (if I understood it correctly) "not later than 1pm."
No; that means "around 1pm" (could be a little earlier, could be a little later).
"not later than 1pm" would be spätestens um dreizehn Uhr.
Can it be used similarly with days?
No. gegen Freitag sounds as wrong to me as um Freitag. Those prepositions simply aren't used with days.
Does the sentence mean that he will come on monday as the latest possibility, and not the days after it
or that on mondays he comes late (he comes around 7 on all other days, but on monday he comes around 8)?
That would be "He comes latest on Monday" / Am Montag kommt er am spätesten / Er kommt am Montag am spätesten / Am spätesten kommt er am Montag