Hey Jan,
You're doing a couple things wrong. Firstly, you shouldn't be checking for updates on every start. What if the user starts your app 20 times a day - will you really be releasing a new update every half hour? It's better to recheck every week.
Secondly, even if you're not using our UI, the AutomaticUpdater can (and does) handle most of the work for you. Set the "UpdateType" to "Automatic". Then you can set "DaysBetweenChecks" to something reasonable (default is 12). Also, you can use the "WaitBeforeCheckSecs" property to tell the AutomaticUpdater to only check N seconds after your app has loaded (this delayed checking gives your app a chance to start before front loading it with more tasks to do).
The checking for new update returns ChekingFailed and the message is: "Update did not complete the previous step..." etc..
Which means the AutomaticUpdater is doing something else (e.g. downloading or extracting an update) while you're trying to force a recheck. This exception is to be expected (do you really need to check for new updates while you're installing updates?).
The UpdateStepOn says UpdateAvailable though I've already updated to the latest version.
This shouldn't happen. First fix the other problems - tell me if this still happens after you've cleaned out the unnecessary code.
Tell me if this helps.