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'.
That may be the formal way to write that sentence but I've never heard anyone say that with 'sedang'.
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'.
Why is it wrong to use 'untuk' after mencari?
What is the difference between mencari and melihat
Mencari = to search for or to look for something
Melihat = to see something