100% Agreed, this is a great suggestion. I have been doing this for years now but in a very round-a-bout way - which is fine for us as a small-medium business with less than 15 Employees but I understand how it would most likely not be practical for medium-large businesses.
When processing a 'Pay Employee' I utilise the area in 'Memo' to add the types of notes like you've mentioned (see screeshot attached) and have always thought how handy it would be if these "notes" were automatically then recorded in the Employees 'Contact Log'. So to work around this when the Payroll Run has been processed I go back via the journey to the relevant employee/s transaction, open it, copy the notes and them paste them into their contact log.
Fiddly process but I believe well worth it for those times when you do need to look back, and of course when identified, you can then drill in further if required.