The Selection Change Sub will never be so slow that it is noticable. You can make it a bit faster with copy and Paste Special and Transpose, but...
The looping in the Worksheet Change sub can really be sped up.
Mixing and matching everybody elses contributions, I may have added a little speed.
Private Sub Worksheet_Change(ByVal Target As Range)
Dim cell As Range
Dim RangeOfResponsibility As Range
Dim CellsToCheck As Range
Dim History As String
'ActiveSheet.Unprotect 'Follow Ken's advice in post #2
Set RangeOfResponsibility = Range(Cells(21, 9), Cells(Rows.Count, Columns.Count))
'If possible, Do nothing
If Intersect(Target, RangeOfResponsibility) Is Nothing Then Exit Sub
'--------------------------------------------------------------
'A little more speed from Paul's very important contribution.
With Application
.ScreenUpdating = False
Calculation = xlCalculationManual
.EnableEvents = False
End With
'--------------------------------------------------------------
'Do as little as possible
Set CellsToCheck = Intersect(Target, RangeOfResponsibility)
'p45cal's algorithm, highly modified for speed.
For Each cell In CellsToCheck
With cell
History = Now & " - " & .Value & " - " & Application.UserName
'Assumption: The length of the String above will never be longer than 255 characters
'Check most common state first
If Not .Comment Is Nothing Then
'Keep oldest history at beginning of Comment.
History = .Comment.Text & vbLf & History
'Work away from the cell as much as possible
Do While Len(History) > 255
History = Mid(History, InStr(1, History, vbLf, vbTextCompare) + 1)
Loop
Else: .AddComment
End If
.Comment.Text History
.Comment.Shape.TextFrame.AutoSize = True
End With
Next cell
'--------------------------------------------------------------
With Application
.EnableEvents = True
.ScreenUpdating = True
.Calculation = xlCalculationAutomatic
End With
'--------------------------------------------------------------
End Sub
To put the History in the comment with the newest history at the beginning of the comment, subsitute these two lines in the code above
History = History & vbLf & .Comment.Text
History = Left(History, InStrRev(History, vbLf, -1, vbTextCompare) - 1)