First-principles statistical mechanics approach to step decoration at solid surfaces