There are a couple of things: step takes a pair of endpoints {a, b} but returns an Interval -- which is not a suitable input for the next step call.
Also, the iterations will run forever, because a and b never change, so Abs[b -a] > eps is always true.
starts with expr, then repeatedly applies f until applying test to the result no longer yields true.
Unless I’ve made some mistake, avoiding for the moment NestWhile and all of that, just testing the single step
step[f, 1, {5, 17}]
does not seem to return what I think you need.
Perhaps before trying to loop off towards infinity with NestWhile, just do one step and see what you get
and then do another step with the result of that and see if that is making progress.
It is not at all clear what you are planning on doing with # and & in this example.