OpenCV 3: Using k-Nearest Neighbors to analyse RGB image
I found a way to get rid of the python loop. np.vstack() converts the image to a single row which in this case is the format findNearest() expects.

Running below code through IPythons timeit function yields a huge perfomance boost:
The version in the original answer takes 2.5s per loop.
The new version runs at 15.3ms per loop.

import cv2
import numpy as np

imgPath = r"../Images/landscape2.jpg"
img_BGR = cv2.imread(imgPath)
if img_BGR is None:
    raise FileNotFoundError("'{0}' could not be opened!".format(imgPath))

BGR_COLORS = dict(blue=(255, 0, 0), green=(0, 255, 0), red=(0, 0, 255), black=(0, 0, 0), white=(255, 255, 255))
LABELS = dict(blue=np.array([0]), green=np.array([1]), red=np.array([2]), black=np.array([3]), white=np.array([4]))
trainData = np.array([BGR_COLORS['blue'], BGR_COLORS['green'], BGR_COLORS['red'], BGR_COLORS['black'], BGR_COLORS['white']], dtype=np.float32)
responses = np.array([[LABELS['blue']], LABELS['green'], LABELS['red'], LABELS['black'], LABELS['white']], dtype=np.float32)

knn = cv2.ml.KNearest_create()
knn.train(trainData, cv2.ml.ROW_SAMPLE, responses)

img_vstacked = np.vstack(img_BGR).astype(np.float32)
ret, results, neighbours, dist = knn.findNearest(img_vstacked, 1)

height, width, depth = img_BGR.shape
results_int = results.reshape(height, width).astype(np.uint8)


def colorPixels(image, results, colorName):
    image[results[:, :] == LABELS[colorName]] = BGR_COLORS[colorName]

img_clustered = img_BGR.copy()
for colorName in BGR_COLORS.keys():
    colorPixels(img_clustered, results_int, colorName)

cv2.imshow("Original vs. Clustered", np.hstack((img_BGR, img_clustered)))
cv2.waitKey(0)
cv2.destroyAllWindows()