This looks like a good paper on the history of malaria. (Click on “download PDF” and you get the option of downloading a zip of the paper plus several related ones.)
Dysentery is a symptom of multiple kinds of infections and not a single disease.
A disease could be “always with us”, in that the disease might have predated our speciation. Yes, we often say that diseases are limited to affecting a single species, but that’s not entirely true: A disease could very well affect two different but closely-related species. In fact, there are some diseases that affect even widely-separated species, like some strains of flu that can infect both humans and birds.
I’m going to ask you to clarify what you mean by this. Why would infectious disease every not have been with us? Dysentery, an intestinal infection cause diarrhea strikes all animal that eat bad food or drink bad water. Have you truly never heard of a dog or cat getting diarrhea for days and then dying? Its been mention just on this forum. Do you believe polio, for example, wouldn’t have affected early humans? Because chimpanzee can afflicted with polio.
According to a book I read, cholera did not exist before civilization. Archaeologists were unearthing Mohenjo Daro and were baffled the complete lack of separation between the sewage streams and the drinking water streams - the two were only separated by a fiber mesh. “How did everyone not die of cholera?” they wondered. The archaeological record showed that the people suffered a mysterious die-off after many centuries of prosperity and speculated that cholera came upon them late in the game - and found its first niche in human civilization.