Should an arXiv paper indicate the conference it was rejected from? We have had a couple of papers rejected from conferences quite a while ago, and we now would like to post them in arXiv. We are considering indicating on the paper which conference it was rejected from, mostly to state when the paper was actually written (we are also writing a new paper with additional results). Is this an acceptable practice?
No, you should not do that. Rejections are not to be advertised. Everyone who will read the paper will be prejudiced against it and you simply do not want that. After all, many papers are initially rejected before being accepted at a suitable venue. You want other people to know when your work got finally accepted and not the other way around. 

If you want to establish the initial date of the paper, next time I would suggest to upload immediately after rejection and after addressing the reviewers' comment that lead to your rejection. This way, you have a better paper uploaded, you establish priority before submitting to the next conference and you can cite your work in subsequent publications.