Ubuntu 16.04 Docker CE not working 'dependency job for docker.service failed'

Hey all,
I try to run docker on a Ubuntu vServer.

I installed docker ce according to the official documentation (https://docs.docker.com/install/linux/docker-ce/ubuntu/#install-using-the-repository)

My OS
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.5 LTS"
NAME="Ubuntu"
VERSION="16.04.5 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.5 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial

Kernel Version:
Linux 4.4.0-042stab134.8 x86_64

When I run the last installation step (
sudo apt-get install docker-ce)

In the Terminal following message occurs:
A dependency job for docker.service failed. See 'journalctl -xe' for details. docker service couldn't start.

journalctl -xe gives following output:
Jan 08 18:02:21 euve264780 sudo[618]: pam_unix(sudo:session): session opened for
Jan 08 18:02:26 euve264780 sudo[618]: pam_unix(sudo:session): session closed for
Jan 08 18:02:45 euve264780 sudo[621]: micha : TTY=pts/0 ; PWD=/home/micha ; US
Jan 08 18:02:45 euve264780 sudo[621]: pam_unix(sudo:session): session opened for
Jan 08 18:02:48 euve264780 sudo[621]: pam_unix(sudo:session): session closed for
Jan 08 18:02:52 euve264780 sudo[712]: micha : TTY=pts/0 ; PWD=/home/micha ; US
Jan 08 18:02:52 euve264780 sudo[712]: pam_unix(sudo:session): session opened for
Jan 08 18:02:52 euve264780 sudo[712]: pam_unix(sudo:session): session closed for
Jan 08 18:03:01 euve264780 sudo[714]: micha : TTY=pts/0 ; PWD=/home/micha ; US
Jan 08 18:03:01 euve264780 sudo[714]: pam_unix(sudo:session): session opened for
Jan 08 18:03:03 euve264780 sudo[714]: pam_unix(sudo:session): session closed for
Jan 08 18:03:07 euve264780 sudo[898]: micha : TTY=pts/0 ; PWD=/home/micha ; US
Jan 08 18:03:07 euve264780 sudo[898]: pam_unix(sudo:session): session opened for
Jan 08 18:03:08 euve264780 sudo[898]: pam_unix(sudo:session): session closed for
Jan 08 18:03:13 euve264780 sudo[903]: micha : TTY=pts/0 ; PWD=/home/micha ; US
Jan 08 18:03:13 euve264780 sudo[903]: pam_unix(sudo:session): session opened for
Jan 08 18:03:14 euve264780 sudo[903]: pam_unix(sudo:session): session closed for
Jan 08 18:03:19 euve264780 sudo[1004]: micha : TTY=pts/0 ; PWD=/home/micha ; U
Jan 08 18:03:19 euve264780 sudo[1004]: pam_unix(sudo:session): session opened for
Jan 08 18:03:19 euve264780 sudo[1004]: pam_unix(sudo:session): session closed for
Jan 08 18:03:27 euve264780 sudo[1048]: micha : TTY=pts/0 ; PWD=/home/micha ; U
Jan 08 18:03:27 euve264780 sudo[1048]: pam_unix(sudo:session): session opened for
Jan 08 18:03:28 euve264780 sudo[1048]: pam_unix(sudo:session): session closed for
Jan 08 18:03:33 euve264780 sudo[1057]: micha : TTY=pts/0 ; PWD=/home/micha ; U
Jan 08 18:03:33 euve264780 sudo[1057]: pam_unix(sudo:session): session opened for
Jan 08 18:03:35 euve264780 sudo[1057]: pam_unix(sudo:session): session closed for
Jan 08 18:03:37 euve264780 sudo[1241]: micha : TTY=pts/0 ; PWD=/home/micha ; U
Jan 08 18:03:37 euve264780 sudo[1241]: pam_unix(sudo:session): session opened for
Jan 08 18:03:41 euve264780 modprobe[1308]: modprobe: ERROR: …/libkmod/libkmod.c:
Jan 08 18:03:41 euve264780 modprobe[1308]: modprobe: FATAL: Module overlay not fo
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.247607438Z” l
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249405988Z” l
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249488891Z” l
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249507681Z” l
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249581621Z” l
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249614924Z” l
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249713529Z” l
Jan 08 18:03:41 euve264780 sudo[1241]: pam_unix(sudo:session): session closed for
Jan 08 18:03:51 euve264780 sudo[1322]: micha : TTY=pts/0 ; PWD=/home/micha ; U
Jan 08 18:03:51 euve264780 sudo[1322]: pam_unix(sudo:session): session opened for
Jan 08 18:03:52 euve264780 sudo[1322]: pam_unix(sudo:session): session closed for
Jan 08 18:04:23 euve264780 su[609]: pam_unix(su:session): session closed for user
lines 267-308/308 (END)
Jan 08 18:02:21 euve264780 sudo[618]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:02:26 euve264780 sudo[618]: pam_unix(sudo:session): session closed for user root
Jan 08 18:02:45 euve264780 sudo[621]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/apt-get purge docker-ce
Jan 08 18:02:45 euve264780 sudo[621]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:02:48 euve264780 sudo[621]: pam_unix(sudo:session): session closed for user root
Jan 08 18:02:52 euve264780 sudo[712]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/bin/rm -rf /var/lib/docker
Jan 08 18:02:52 euve264780 sudo[712]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:02:52 euve264780 sudo[712]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:01 euve264780 sudo[714]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/apt-get update
Jan 08 18:03:01 euve264780 sudo[714]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:03 euve264780 sudo[714]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:07 euve264780 sudo[898]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/apt-get install apt-transport-https ca-certificates curl sof
Jan 08 18:03:07 euve264780 sudo[898]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:08 euve264780 sudo[898]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:13 euve264780 sudo[903]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/apt-key add -
Jan 08 18:03:13 euve264780 sudo[903]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:14 euve264780 sudo[903]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:19 euve264780 sudo[1004]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/apt-key fingerprint 0EBFCD88
Jan 08 18:03:19 euve264780 sudo[1004]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:19 euve264780 sudo[1004]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:27 euve264780 sudo[1048]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/add-apt-repository deb [arch=amd64] https://download.docker
Jan 08 18:03:27 euve264780 sudo[1048]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:28 euve264780 sudo[1048]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:33 euve264780 sudo[1057]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/apt-get update
Jan 08 18:03:33 euve264780 sudo[1057]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:35 euve264780 sudo[1057]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:37 euve264780 sudo[1241]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/apt-get install docker-ce
Jan 08 18:03:37 euve264780 sudo[1241]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:41 euve264780 modprobe[1308]: modprobe: ERROR: …/libkmod/libkmod.c:514 lookup_builtin_file() could not open builtin file '/lib/modules/4.4.0-042stab134.8/
Jan 08 18:03:41 euve264780 modprobe[1308]: modprobe: FATAL: Module overlay not found in directory /lib/modules/4.4.0-042stab134.8
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.247607438Z” level=warning msg="Error while setting daemon root propagation, this is not generally cr
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249405988Z” level=info msg=“libcontainerd: started new containerd process” pid=1316
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249488891Z” level=info msg=“parsed scheme: “unix”” module=grpc
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249507681Z” level=info msg=“scheme “unix” not registered, fallback to default scheme” module=grpc
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249581621Z” level=info msg="ccResolverWrapper: sending new addresses to cc: [{unix:///var/run/docker
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249614924Z” level=info msg=“ClientConn switching balancer to “pick_first”” module=grpc
Jan 08 18:03:41 euve264780 dockerd[1307]: time=“2019-01-08T18:03:41.249713529Z” level=info msg=“pickfirstBalancer: HandleSubConnStateChange: 0xc4209d5030, CONNECTING” m
Jan 08 18:03:41 euve264780 sudo[1241]: pam_unix(sudo:session): session closed for user root
Jan 08 18:03:51 euve264780 sudo[1322]: micha : TTY=pts/0 ; PWD=/home/micha ; USER=root ; COMMAND=/usr/bin/docker container run hello-world
Jan 08 18:03:51 euve264780 sudo[1322]: pam_unix(sudo:session): session opened for user root by root(uid=0)
Jan 08 18:03:52 euve264780 sudo[1322]: pam_unix(sudo:session): session closed for user root
Jan 08 18:04:23 euve264780 su[609]: pam_unix(su:session): session closed for user micha

If I run
sudo docker container run hello-world

I got following output:
Docker: Cannot connect to the Docker daemon at unix:///var/run/docker.sock. Is the docker daemon running?

Anyone an idea?
Thanks a lot