According to the group, the best solution for counting entities is:

What Alfred describes is how countEntities is implemented. it simpy(?) does a normal query with a limit of 0 and a max_int offset. The count is then available via the response.batch.skipped_results (where response is the RunQueryResponse returned by RunQuery), however it may be necessary to run the query multiple times starting from reponse.batch.skipped_cursor if response.batch.more_results is not NO_MORE_RESULTS/MORE_RESULTS_AFTER_CURSOR.

https://groups.google.com/forum/#!topic/gcd-discuss/wH8lVOA-a8Y

This was made possible by this ticket.
#3279

However, currently the setLimit enforces a value > 0.

    @Override
    public B setLimit(Integer limit) {
      Preconditions.checkArgument(limit == null || limit > 0, "limit must be positive");
      this.limit = limit;
      return self();
    }

https://googleapis.github.io/google-cloud-java/google-cloud-clients/apidocs/com/google/cloud/datastore/StructuredQuery.Builder.html#setLimit-java.lang.Integer-

StructuredQuery.java needs to be updated to allow a limit >= 0.

https://github.com/googleapis/google-cloud-java/blob/master/google-cloud-clients/google-cloud-datastore/src/main/java/com/google/cloud/datastore/StructuredQuery.java#L760

This will allow the following code to work:

        int count = 0;
        Query query = Query.newKeyQueryBuilder().setKind(kind)
                .setOffset(Integer.MAX_VALUE).setLimit(1).build();
        results = datastore.run(query);
        for (count = results.getSkippedResults(); results.getMoreResults() != QueryResultBatch.MoreResultsType.NO_MORE_RESULTS; i++) {
            query = query.toBuilder().setStartCursor(results.cursorAfter).build();
            results = gdatastore.run(query);
            count += results.getSkippedResults();
        }