Count Matches to a Kernel
Besides what is discussed below (see for instance the above Cris Luengo's comment): for reasonably-sized images, and modern computing techniques, I can see no reason in practice why the basic template match counting could be slow, and why one should look for faster, imprecise and incomplete alternatives.

[UPDATE 20180730]
You are trying to compare matches in a pair of matrices. Ontologically, the comparison operation  is not a linear operation. Hence, no convolution operation, naturally linear, seems be the easiest approach. Neither the FFT or Fourier stuff in general, as they are quite related to linearity.

IMHO, you ought to look at the concept of Template Matching, and avoid the notion of kernel, which is a debated notion.

Instead, a simple counting approach could do the job. For instance in Matlab:

%% The OP kernel and image
% dataKernel = [1 2 1;1 2 1;1 2 1;];
% dataImage = [1 1 2 1 2;1 1 2 1 2;1 1 2 1 2;];

%% A random kernel and image
dataKernel = floor(256*rand(64,64));
dataImage = floor(256*rand(300,300));

%% Compute sizes
[nRowKernel,nColKernel] = size(dataKernel);
[nRowImage,nColImage] = size(dataImage);

[nRowCrop] = nRowImage - nRowKernel+1;
[nColCrop] = nColImage - nColKernel+1;

lMatch = zeros(nRowCrop,nColCrop);
dataImageCrop = zeros(size(dataKernel));

tic;
for iRowCrop = 1:nRowCrop;
    for iColCrop = 1:nColCrop;
        dataImageCrop = dataImage(iRowCrop:iRowCrop+nRowKernel-1,iColCrop:iColCrop+nColKernel-1); % Crop a portion of the image
        lMatch(iRowCrop,iColCrop) = length(find(dataImageCrop - dataKernel == 0));
    end
end


Here, I just used an ad-hoc displacement for the crop, but than could be automated easily. No product, just differences. If your data are limited size integer, there might be more options for speed. But even in Matlab, this is relatively fast. 

FFT-based cosine similarity for fast template matching seems to better explain what is alluded too in OpenCV performance on template matching (provided by the OP). If the image is of size $I_x \times I_y$, and the template is  $T_x \times T_y$, with $T_x &lt; I_x$ and  $T_y &lt; I_y$, you can expect a number of operations of:


$O(I_xI_y  T_x T_y)$ with the standard comparison,
$O(I_xI_y\log I_x \log I_y)$ with a Fourier method.


From afar, Fourier might seem to be beneficial whenever $\log I_x \log I_y &lt;  T_x T_y$. But:


this is only an asymptotic result the constant behind the $O(\cdot)$ can make a huge difference
then you have to find maxima, which add to the overall cost
the hardware implementation (pipeline, CPU/GPU) can made a lot of difference in practice, compared to number of operations
indeed, the first one only require adds/subtracts and absolute values on integers,  the second complex operations on floats; thus, there might be huge variations between implementations
a difference of pixels, like the sum of absolute difference (SAD) does not translate easily in Fourier because it is orthogonal
implementing fast correlations, the FFT might be able to provide you with a "best match", but it is not local, so I cannot imagine right now how this can directly give you a count by patch location.


So far, to me:


if you only want a best match, then you can do Fourier on the whole image;
if you really want (even approximate) counts at all template locations, I do not see an easy and useful Fourier implementation for that so far.


However, you can speed the matching up, with several tricks, like using the symmetry of the template (if any), the integral image, multiscale pyramid-like matching, etc. A few additional pointers:


Fast Template Matching
Fast Template Matching With Polynomials
FasT-Match: Fast Affine Template Matching - The Computer Vision ...
Very Fast Template Matching