If I change it to Use URL rewriting and then rename the htaccess without the .txt - the landing page works fine, however the articles and other pages return a 404 error.
I tried some guides that talk about SEF404 (or whatever its called) settings in K2 but got nowhere fast.
Renaming htaccess.txt to .htaccess is usually enough. It should not be renamed to htaccess
.htaccess can be tricky because you might have another .htaccess or httpd.conf that might be overriding the .htacces that you have in your Joomla directory.