Symptoms

Running registration wizard would show the error "A newer version of the K2 for SharePoint App is available. See http://help.k2.com/en/KB001610.aspx for more information."

Running through "K2 for SharePoint Setup Manager", "K2 for SharePoint - App Deployment" will fail on "User Profile Sync Connection Task".
 

Diagnoses

K2 for Sharepoint had just recently been updated on this environment and the app had been updated in the app catalog. Sharepoint site however says it does not have the most recent version of K2 for Sharepoint App
 

Resolution

We removed and re-added the K2 for SharePoint app and everything was working as expected after that.