Cannot start session for anonymous user
It's not necessary to use a private temp store for anonymous user if you don't have a lot of data. And for anonymous it's not so easy to implement this.

To store data for anonymous users you can simply use the php $_SESSION variable.

$_SESSION['my_module']['data'] = 'My Data';


Drupal will take care of starting and saving the session.

Edit:

OK, to make this official, you should use the request object. See https://www.drupal.org/node/2380327. But drupal core and contrib code still uses the $_SESSION variable. This should be OK at least for D8.

In both cases you have not to handle the session yourself. Drupal will load the session if there is one present when it begins with the request. And drupal will start a new session and saves it at the end of the request, if there is newly added session data.