I have no idea whether this is directly or indirectly related to K2, but you guys tend to give good support here B)

After I uploaded my site from WAMPServer localhost to a live IIS server, almost any link I click on, item title, read more, category name or comment gives me 404. It all was working fine on localhost. Any idea?

I think you should use an apache/nginx server. The 404 links are due to IIS not supporting .htacess. You need to follow this tutorial docs.joomla.org/IIS

Yes I suspected it was an IIS issue and not a K2 issue. I somehow solved it by disabling URL rewriting in Site settings.

Thanks.