Garbo gave you good advice regarding turning the screen updating off then turning it back on at the end of the macro. But Garbo is definitely wrong that you need to select each cell. That would make the macro run longer than it should. You are doing the right thing by not selecting the cells.
What you want to do is go under the worksheet's Change event in Visual Basic Editor. The change event occurs every time someone makes a change to a cell in that worksheet. The change occurs to the cell called the Target cell which is a range. Then what you'll want to do is find the intersect of the Target cell and the range you called MyRange. The intersect method finds what cells two ranges have in common. If the two ranges have cells in common it will result in a range, otherwise you will end up with a result of Nothing.
Dim MyRange As Range, MySelectedRange As Range
Set MyRange = [K4:K117]
Set MySelectedRange = Intersect(Target, MyRange)
Application.ScreenUpdating = False
If MySelectedRange Is Nothing Then
'Here's where you put your For...Next loop.
End If
Application.ScreenUpdating = True
End Sub
Basically the macro as I put it should run if the Intersect of MyRange and Target yields a result of Nothing. That means that the Target cell (the cell that was changed) was not inside MyRange, so the macro will start updating the cells in MyRange.
Cozmosis is right. It would be best if you used Select Case in this instance it's easier. It also would be best to use With/End With so you don't have to keep typing Cell.Interior.ColorIndex. It will also make the macro run slightly faster.
I created a version that works, the full code looked like this:
Private Sub Worksheet_Change(ByVal Target As Range)
Dim MyRange As Range, MySelectedRange As Range
Dim x As Range
Set MyRange = [K4:K117]
Set MySelectedRange = Intersect(Target, MyRange)
Application.ScreenUpdating = False
If MySelectedRange Is Nothing Then
MsgBox "MySelected Range is Nothing"
For Each x In MyRange
With x.Interior
Select Case x.Value
Case "Dependent"
.ColorIndex = 44
Case "Not started"
.ColorIndex = 15
Case "In progress"
.ColorIndex = 37
Case "In progress, late"
.ColorIndex = 3
Case "Finished"
.ColorIndex = 43
Case Else
.ColorIndex = xlNone
End Select
End With
Next x
End If
Application.ScreenUpdating = True
End Sub