J'avais le même problème, la solution je l'ai trouvé sur ce site.
http://steamcommunity.com/app/211420/discussions/0/648814843502183547/?insideModal=1
Si tu suis les étapes comme indiquer, t'auras aucun problème pour le faire fonctionner.
En gros, ça dit qu'il faut que tes 2 .exe de ton dossier dark souls soit en mode de compatibilité windows 7 pour qu'il puisse se lancer.
Ensuite, il te faut désinstaller Microsoft Games for Windows Marketplace et Microsoft Games for Windows - LIVE Redistributable de ton PC puis redémarrer ton PC puis réinstaller leur dernières versions.
Avant d'installer, il est important de choisir le mode de comptabilité windows 7 et d'exécuter en tant qu'administrateur.
Une fois l'installation réussie, le jeu devrait pouvoir se lancer tout comme GFWL.
Si ça ne fonctionne pas, installer l'assistant de connexion windows live.
Méthode 100% fonctionnel, j'avais des galères pas possible avec windows 8.1 pour lancer le jeu et maintenant ça marche nickel.