This error says that Let's Encrypt couldn't communicate with your server over http (TCP port 80). If you can share your real domain I could check that for you, otherwise you need to double check that TCP port 80 traffic is indeed reaching the correct machine. Checking from your phone using the mobile network is often a good test.
As well as firewalls, you need to look out for domains sometime pointing to IPv6 addresses (having a AAAA record in DNS) which inevitably end up pointing to a server run by your DNS host instead of your actual server. You can diagnose that using https://letsdebug.net/
No valid A or AAAA records could be ultimately resolved for autodiscover.xxxx-xxxxxx.fr. This means that Let's Encrypt would not be able to connect to your domain to perform HTTP validation, since it would not know where to connect to.
Yes you will need your autodiscover record to also point to the same server otherwise you won't be able to get a certificate for it using http validation.
You could use DNS validation instead but that's a little more complicated and depends on whether your DNS provider is supported for automated updates.