I have some computer science students in a compulsory introductory programming course who see a programming language as a set of magic spells, which must be cast in order to achieve some effect (instead of seeing it as a flexible medium for expressing their idea of solution).

They tend to copy-paste code from previous, similar-looking assignments without considering the essence of the problem.

Are there some exercises or analogies to make these students more confident that they can, and should, understand the structure and meaning of each piece of code they write?

You could present them a series of exercises, each one building on the previous while adding some extra element or twist to the problem, or investigating the issue from a different perspective, which reveals a weakness of the previous solution, requiring a new, different approach. This forces them to think about, analyse, modify and experiment with each solution, instead of just copy-pasting a ready-made piece of code.
Another possibility - although not strictly a programming task - is to ask them to estimate various things. E.g. how much water flows through the Mississippi delta per second? Such questions don't have a set answer, especially because one needs to make certain assumptions to get to a convincing (range of) value(s). And - although answers to many of these "classic" ones can be googled indeed - you can easily make up new ones which aren't (yet) found anywhere on the net.
Examples to both of these kinds of exercises can be found in e.g. Programming Pearls by Jon Bentley. Also The Pragmatic Programmer has some good challenges.
A third kind of task would be to present them some piece of code with (one or more) bugs in it, which they must find and fix. This again forces them to use their analytical skills and reason about how the program is actually working.
Update
Feedback from a comment by Billy ONeal:

The problem with the "series of exercises" is that students who have a problem with an earlier exercise are completely screwed for remaining exercises.

You are right, although I feel this is more about the general problem of setting course difficulty to the right level / grouping students of similar skill level together. Moreover, one can arrange the students into smaller groups where they are required to discuss and debate about the problems and solutions, and solve the problems together. If someone doesn't get it, the others can help (this setup would improve teamwork skills too). And if someone tries to be lazy and let the others do all the work, it is surely noticed by the teacher (who is supposed to be walking around, supervising and mentoring the students, not playing WoW on his laptop in the corner ;-)
And one can also adjust the exercises to accommodate students with different skill levels. Beginners can go slower, experienced ones faster.
