I had the same issue. I un-installed the Web Deploy from "Add/Remove Programs". I then re-downloded Web deploy 4.0 (https://www.microsoft.com/en-us/download/details.aspx?id=106070) .
After that it all worked!