Gee, I guess I need to learn more about these "cell phone" devices. I had no idea that putting one in your backpack could help you cheat on a test.
And I had no idea that teachers could keep an eye on every student during every minute of a test to make sure they never took it out and held it under their desk.
Do calculators also have this ability?
I have no problem with calculators also being banned from classrooms during tests for which they could be used to cheat. Other than that, I see no reason to ban calculators, since they're unlikely to cause any other disruptions or problems, and are in fact necessary for certain classes.
As for paper, the information which it can contain is limited by its size. Any piece of paper large enough to contain more information than the kid could easily remember would be easy to spot. And, even in this digital age, I also imagine paper is still a requirement for a lot of classes.
Also, unlike the examples you mention, cell phones can be used for communication between students during tests, which is, in my opinion, the real danger.
If the class is disrupted, or the staff is annoyed, by a cell phone in someone's backpack, I think that there are issues other than the cell phone that need to be addressed.
Maybe, but those issues may not be the school's concern. Maintaining order and a constructive working/learning environment is, and keeping cell phones out of the picture is a perfectly legitimate way to do it.
ETA: I'd also wonder why, if the student has no intention of using the cell phone during class, he'd care if it was in his backpack as opposed to his locker.
So, the short answer is that schools should be allowed to ban cell phones because doing so might help solve some practical problems, and does not represent an unacceptable violation of the students' rights.