What approaches could be used to teach a model to make appropriate brush strokes to reproduce a painting?
Main Idea:

The main idea is the you could measure how good is the output and the input of your model simply representing it by some mathematical object, for example a vector in a high dimensional space and then using some error function to measure the fitness (how good your model is performing).

A possible formalization

The scenario your describing fits in a more general optimization function, the most general optimization scenario is;

$$ min_{x \in X} f(x) $$

where $X$ is the domain. In the case of image processing and computer vision $x$ is a matrix of pixels, this matrix of pixels can be represented by a vector $x \in \mathbb{R}^{m \times n}$. In the case you describe you could also represent the input (painting) as a vector $y\in \mathbb{R}^{m \times n}$. 
Then $f$ coul be RSME between some $x$ and $y$, i.e. $f(x) = {\| y - x \|}_2$. Notice that $y$ is given and it does not change. 

Now the key question here is how to represent a stroke, or more formally a function the values of $x$. A very basic idea can be represent the stroke by the following tuple $(o, e, t, c)$ where $o$ and $e$ are two dimensional points, the origin and the end of the stroke; $t$ is the thickness of the stroke and $c$ is the color of the stroke. Let $S$ be the space of all the strokes, assuming the thickness and colors are finite, S is finite. The possible pairs of $o$ and $e$ are finite namely all the pairs of possible points in $m \times n$. Now let $S^k$ be the composition of $S$ with itself $k$ times. 

Finally the problem can be represented the following way:

$$\min_{s \in S^k}{\| y - t(s, x) \|}$$

Where $t$ is the function that applies $s$, that is a number of different strokes to an empty canvas $x$, by empty canvas I mean a matrix full of zeros. 

Summarizing the ideas expose above are a possible formalization of your problem, of course is not the only one. The main issue is that the robot does not "learn" is simply computes the optimal set of strokes to apply.

Other ideas

Another possible approach is to use reinforcement learning, this learning paradigm does not needs labeled training samples, it relies in a reward function $R$ to guide the learning process. Also if defines a set of states and actions the agent can be or do. The states could be the strokes and the actions add another stroke, the reward function can be a variation of the error function. Also I am far from being an expert in reinforcement learning I guess is worth looking into it.

A proven approach

The problem you describe has been demonstrated in real life. See this paper: Feedback-guided Stroke Placement for a Painting Machine. The paper demonstrates a system that describes your scenario, also see this site for more work of the authors or this for the site of the project.