Is there any remotely efficient way to determine whether a graph can be disconnected by the removal of fewer than k edges, or even one that has a lower asymptotic complexity than just trying each set of k-1 edges?

If it helps, you can assume the graph is k-regular that k is much smaller than the number of vertices.