The question asked in the title is not at all the same as the fist question in the body of the text. Because any meaningful answer to the latter seemingly presupposes (wrongly in my opinion) the existence of a mechanism to ascertain if a non-human animal has made an abstract connection in the scientific consensus, I will simply note that paternal care is rare among non-human primates and apparently non-existent among our closest kin and so that the connection between sexual activity and fecundation is in all likelihood a learned fact, not part of our core evolved cognitive abilities.
As far as I know, parietal art, though it contains exaggerated depiction of both sexual organs and of gravid women (Venus figures), gives no indication of a link between the two (though it is somewhat hard to decide what would count as uncontroversial evidence).
On the other hand, Egyptian papyri abounds in detailed gynecological knowledge, complete with accurate early prognosis for pregnancy and contraception advice. So the absolute upper historical bound for this connection is 1800 BCE, the time of writing of the Kahun papyrus. I will also note that the Code of Ur-Nammu, written around 2100BCE and one of the oldest known written text, deals largely with deflowering, offsprings produced by a couple of slaves, by a couple formed of a slave and a free person etc. This strongly suggests that the connection between sex and procreation was perfectly well understood by the writers of this code. Likewise, paternal as well as maternal lineage is very clearly understood in the Pyramid texts dating from around 2400 BCE.
To sum up, there are no evidence that the connection was understood in pre-historical time, just as there is no or scarce evidence for any abstract knowledge in pre-historical time almost by definition. However, evidence that the connection was very well understood is almost contemporary with the oldest known written texts.