First off, why are you storing the "city" in a table where it is repeated? It appears to be tied to the car, if so then just store it in the car/city/dates table and use a vlookup if it must be in the other table. This will save on potential mistakes...
In answer to your question, here is how I've set up a sheet to test this, you will have to adapt the below code to suit your data layout:

Firstly, format all cells in the table as green/available. This macro will then change all the booked cells.
Sub bookings()
' This finds the number of rows in the top table (-1 for heading row)
Dim numCars As Integer
numCars = ActiveSheet.Range("A1").End(xlDown) - 1
' Tracks the active car row
Dim carRow As Integer
' Cells for first row/colum cells in tables
Dim dateCell As Range
Dim bookingCell As Range
' cycle through the bookings table (bottom)
For Each bookingCell In ActiveSheet.Range("A10:" & ActiveSheet.Range("A10").End(xlDown).Address)
' Find which row in top table belongs to this booking's car. Could cause error if doesn't exist!
carRow = ActiveSheet.Columns(1).Find(what:=bookingCell.Offset(0, 1).Value, lookat:=xlWhole, LookIn:=xlValues).Row
' Cycle through dates in top table for comparison
For Each dateCell In Range("C1:" & ActiveSheet.Range("C1").End(xlToRight).Address)
' Comparison like this will only work on dates stored properly (not as text)
' If this isn't working, convert your dates by multipling them by 1.
' This can be done in a neighbouring cell like =A1*1, then copying values
' See this link for details:
' http://stackoverflow.com/questions/6877027/how-to-convert-and-compare-a-date-string-to-a-date-in-excel
' If the date lies between the booking dates...
If dateCell.Value >= bookingCell.Offset(0, 2).Value _
And dateCell.Value <= bookingCell.Offset(0, 3).Value Then
With ActiveSheet.Cells(carRow, dateCell.Column)
' Do a check that no manual change has happened
if .value = "Available" then
' Change the text to booked and colour to red
.Value = "Booked"
.Interior.Color = RGB(200, 0, 0)
end if
End With
End If
Next dateCell
Next bookingCell
End Sub