Can one define on the measurable space $(\Omega = \{0,1\}^\mathbb{N}, P(\Omega))$ a measure $\mathbb{P}$ uniform in the sense that sets of sequences with $k$ fixed values should have measure $\dfrac{1}{2^k}$. Note that I require that the measure be defined on all of $P(\Omega)$. I also assume the axiom of choice to be true.
My guess would be it's not possible as my intuition was that since $\Omega$ is in bijection with $\mathbb{R}$, the measurable space looks a bit like $(\mathbb{R}, P(\mathbb{R}))$ which I think cannot have a translation invariant measure supporting Vitali sets for example.
I read this question: Uniform probability measure on $\{0,1\}^\omega$ but the link seems dead. Does Kolmogorov theorem indeed provides a positive answer to my question? I saw the other simple construction from Lebesgue measure but it supports only Lebesgue measurable sets, not all of $P(\Omega)$ as far as I understand.
Actually I suspect that the answer to the question exactly as you asked it is yes: If I recall correctly Lebesgue measure can be extended to a measure on all of $P(\Bbb R)$; what's impossible is a translation-invariant extension.
Which leads to a question you didn't quite ask: If you define an operation making $\{0,1\}$ into a group with identity $0$ then $\Omega$ is a (compact abelian) group. This gives an elegant way to describe the "uniform" measure on a subalgebra of $P(\Omega)$: it's just Haar measure. In fact this Haar measure cannot be extended to a translation-invariant measure on all of $P(\Omega)$.
Exactly like the standard proof of the existence of a non-Lebesgue-measurable set: Say $H$ is a countably infinite subgroup (for example the subgroup generated by any countably infinite subset), and let $C$ consist of one element from each coset. Then $$G=\bigcup_{h\in H}hC,$$so $\mu(C)=0$ implies $\mu(G)=0$, while $\mu(C)>0$ implies $\mu(G)=\infty$.
(If $G$ is not abelian I'll leave it to you to insert the words "left" and "right" in a few places so as to make sense of the above.)