The graphviz installer doesn't add itself to the path, so kcachegrind should try and get the location from the windows registry and use that information to call the tools. The information needed for that can be found in HKLM\SOFTWARE\Wow6432Node\AT&T Research Labs\Graphviz or HKLM\SOFTWARE\AT&T Research Labs\Graphviz which contains a key InstallPath. In the subdirectory bin of the InstallPath you can find the required tools. Since rereading the information on every refresh is probably a stupid idea, one might want to store the results.
This seems to be very specific to the packaging of GraphViz. I can imagine that there are multiple GraphViz packages around, and not all set this key? Which package are you telling about here? Another option would be for the kcachegrind package to be bundled with a local copy of "dot.exe" (ie. not a problem to fix in source code). Anyway, not sure how to look up a registry key, and I also can not test it. Can you try to come up with a patch?
yes, I didn't get the patch ready yesterday, will come in the next days.