How can I formulate the map colouring problem as a hill climbing search problem?
First of all you need an initial solution. You will then improve this solution with hill climbing.

For your initial solution, you can color the map randomly using the K colors. This will most likely result in conflicts (adjacent regions of the same color).

Then the hill climbing part: Find a region which has conflicts and swap its color for another color, making sure that the new color does not incur more conflicts than the old one. With each iteration your solution should slowly improve.

Note that hill climbing is not perfect and that you may not find a feasible solution in the end.