出来る

こんにちは皆さん、

英語で言うかもしれません：
In English I might say:
"Please can I speak to him"

In this sense "can" has the nuance of "will you let me" rather than "am I physically able".

So my question is, if I was to ask this question, would it sound natural to say:
Or is it best to just say something simple like:

ありがとうございます！

It may depends on the context but "please can I speak to him" should be asking for permission, not the ability.
To ask for permission, we usually use ～てもいいですか.

彼と話してもいいですか。

彼に話してもいいですか sounds more like 'may I/can I tell him (something)?'

彼に話すことができてください does not make sense.
彼と話せますか 'can I talk to/with him' is also OK.

彼に話してください means 'please speak to him' or 'please tell him (something)'.

Another option is 彼に話しかけてもいいですか.

Unlike に, と has a nuance of "mutual" as in undrentide-san's translation "with".