How do you do an optimal binary search on a two variable function?

You need to clarify your terminology a little bit. Symmetric about the diagonal? Strictly increasing with respect to which ordering of the pairs?

What I meant by symmetric is f(x,y) = f(y,x), and by strictly increasing, I meant that for x’ >= x and y’ >= y, f(x’,y’) >= f(x,y) with equality only if x’=x and y’ =y

Is there is prescribed relation between f(x,y) and f(x’,y’) when, say, x > x’ and y = y’ ?

What I am thinking of is something like f(x,y) = x^3 + y^3. The idea is that f(x,y) increases if either x or y increases.

Is k guaranteed to be an integer?

Also, am I interpreting your question correctly that it is known in advance some number m such that f(0,m) > k?