Divisibility tests are a useful problem-solving technique for particularly dealing with larger numbers (thousands etc) and algebraic problems. However, I have always found that many students will just reach for the calculator, many not even realising the simpler tests, such as anything divisible by 2, 5 or 10.
What is an effective means to help 'train' these skills in students as a problem solving and 'thinking' skill?
The students are the smart ones. If the calculator is giving the easiest way to get the answer of course the best is to use the calculator.
But what would happen if the problem is so designed that a calculator would be of little or no help.
Calculators don\t help much to show that $n(n+1)$ is even. That $a+10b+100c+1000d$ is divisible by $9$ if and only if $a+b+c+d$ is divisible by $9$. That $3^{3^{3^{3^{3^{3}}}}}-1$ is even.
... and these are still not clever exercises.
Addendum: Because it is relevant, I would like to advocate against training students to mindlessly using some tricks, techniques, procedures. Students in their brute state are critical enough by nature. Pushing them to do some task for which there is not a clear purpose is what turns them into bad students. In mathematics we often focus too much in teaching the techniques, but what is more important is the purpose for those techniques. That is why you often see students that compulsively 'simplify' solutions, even partial solutions, or expand brackets for no reason.
This applies to any technique. Give them exercises in which it is clear the purpose of a technique. Being able to identify a purpose, not knowing lots of procedures, is what makes them able to solve new problems. Procedures and techniques can be googled most of the time.