I don't think that the translation of 'we are looking for that newspaper' is 'kami mencari koran itu', it should be 'kami sedang mencari koran itu'.
Why kami over kita?
It's unclear. I think in this context you can use both. They will use 'kita' when the person they are talking to is a part of 'we'. On the other side, they will use 'kami' when the person they are talking to is not a part of 'we'.
What is the difference between mencari and melihat