This bill would do absolutely nothing at all legally. Here is the operative part of the bill:

   The Fourth Amendment to the Constitution shall not
   be construed to allow any agency of the United States
   Government to search the phone records of Americans
   without a warrant based on probable cause.

The 4th is part of the Constitution. Congress cannot change its meaning with a mere bill. Changing the meaning requires a Constitutional amendment. So, no effect from Paul's bill as far as that goes.

The courts interpret the Constitution, and due to separation of powers, Congress can't tell the courts how to interpret it. So, no effect from Paul's bill here, either. Separation of powers also prevents Paul's bill from having any effect on the executive branch.

To make this sort of thing work, I think you'd have to go to the laws that actually created or authorized the agencies whose behavior you want to change, and amend those laws.