Your linked article says " Smaller values on all metrics correspond to more accurate predictions," (bottom of p.3) so presumably good fits will have values near 0. A better question might be, "What is the cutoff threshhold for a bad fit?"
Regarding the "binomial deviance" metric, the Chess Ratings kaggle contest used it as their evaluation metric and provided the following definition:
$-[Y\log_{10}(E) + (1-Y)\log_{10}(1-E)]$
where Y is the game outcome (0.0 for a black win, 0.5 for a draw, or 1.0 for a white win) and E is the expected/predicted score for White
The metric is undefined for 0 and 100, but values near 0 are good fits and values near 100 are bad fits.
The Kaggle site references Mark Glickman, the current chairman of the US Chess Federation and inventor of the Glicko rating system. Unfortunately they do not provide a specific citation and he has quite a few publications, but if you are interested in learning more about this metric you should dig through his work. http://www.glicko.net/
I can't access the article from my current workstation, but I believe this is the citation:
Glickman, Mark E. "Parameter estimation in large dynamic paired comparison experiments." Journal of the Royal Statistical Society: Series C (Applied Statistics) 48.3 (1999): 377-394.