Minimal number of changes to make string into concatenation of $k$ palindromes
Let $s=s_1 s_2 \dots s_n$.
Suppose that you already know, for each substring $s[i:j]=s_is_{i+1}\dots s_k$ of $s$, the minimum number $D(i,j) $ of character substitutions needed to make $s[i:j]$ palindrome. These values can be found in $O(n^2)$ time using dynamic programming since $D(i,j) = 0$ if $i&gt;j$ and $D(i,j) = D(i+1,j-1) + \mathbb{1}_{s_i \neq s_j}$ if $i \le j$.

Your problem exhibits the optimal substructure property. Suppose that you already known the beginning position $i$ of the last substring $s[i:n]$ of $s$ in an optimal partition: clearly you will need to make $D(i,n)$ changes in order to transform $s[i:n]$ into a palindrome. You are then left with the prefix $s[1:i-1]$ of $s$. This prefix still needs to be partitioned into $k-1$ nonempty substrings that are palyndromes. Fortunately this is exactly an instance of the problem you were trying to solve in the first place. You can exploit this property as follows:

Define $OPT[j,h]$ as the minimum number of character substitutions needed in order to partition $s[1:j]$ into $h$ substrings, each of which is non-empty and palindrome. If no such partition can exist, regardless of the number of character substitutions, let $OPT[j,h]=+\infty$.

By definition $OPT[0,0]=0$  (since $s[1:0]$ is the empty string) and, for $h=1,\dots,k$, $D[0,h] = +\infty$.

Moreover, for $i=1,\dots,n$ and $h=1, \dots, k$:
$$
OPT[j,h] = \min_{i=1,\dots,j} \left\{ OPT[i-1,h-1]  + D(i, j) \right\}. 
$$

This gives you a dynamic programming algorithm with time complexity $O(k n^2)$.
The optimal solution to your original problem is $OPT[n,k]$.