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.