Is it possible to test implementation for side-channel attacks?
At least for compiled languages it should also be possible to have
  tools that perform static analysis on machine code, shouldn't it?


Indeed, such tools exist. There are companies specialized in this domain which provide this kind of tools (see this datasheet for example). But you should note that an only software tool will not be able to detect all weaknesses against certain types of attacks (e.g. some fault injections).


  it should be possible for timing and maybe even cache based attacks


There is also CacheAudit which is a tool for the static analysis of cache side channels (plus, it's free). It can be configured to test your implementation against several architectures (e.g. separate or shared cache for data and instructions) and several attack models. Here is the description of the framework and you can download it here. To put it in a nutshell:


  CacheAudit takes as input a program binary  and  a  cache 
  configuration  and  delivers  formal  security  guarantees  that 
  cover  all  possible  executions  of the corresponding system.