While googling around reading about docker images, I found this comment:
So I added these to my config:
- run: sudo apt-get update
- run: sudo apt-get install -y zlib1g-dev libicu-dev g++
- run: sudo docker-php-ext-configure intl
- run: sudo docker-php-ext-install intl
So that fixed it! Thanks a lot for the tips!