Solved: Unable to start LXC container (Operation not permitted - failed to allocate a pty)

I just realized

devpts /dev/pts devpts rw,relatime,mode=600,ptmxmode=000 0 0

which should actually be

 rw,nosuid,noexec,relatime,gid=5,mode=620,ptmxmode=000

so you could try to remount /dev/pts and try again.