This looks like a bug in Neo4jClient.
As a workaround, try this:
for (var k = 1; k < 10000; k++)
{
var fio = "Radzhab"+k;
var name = "33-333"+k;
client.Cypher
.Match("(user1:User)", "(user2:Phone)")
.Where((Users user1) => user1.Fio == fio)
.AndWhere((Phone user2) => user2.Name == name)
.Create("user1-[:HAVE_PHONE]->user2")
.ExecuteWithoutResults();
}