Let $p$ be a prime. (say 256 bit)
Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such a $q$ exist.
[I know it exists for k =1, I am looking for a large $k$]
There is numerical evidence that for the vast majority of primes $p$, there exists $k$ making $q=2^k\,p+1$ prime. See first exceptions in A137715.
The only practical way I see to find which $(p,k)$ make $q=2^k\,p+1$ prime in the question's context is testing $q$ for primality using a fast test. As noted in the other answer, sieving for small primes can be shared across multiple $k$.
An overly crude approximation of the probability that $q=2^k\,p+1$ is prime is that probability for an integer of same magnitude divisible by neither $2$ nor prime $p$, that is for $p>2$ and by the Prime Number Theorem roughly $\displaystyle\frac{2-2/p}{\ln(q)}$, which we can approximate as $\displaystyle\frac2{\ln(p)+k\ln(2)}$ for our large $p$. A numerical experiment shows that's in the right ballpark, but sizably too high.
A better analysis is that for random large prime $p$, and a small prime $r>2$, the quantity $p\bmod r$ is about uniformly distributed on $[1,r)$, thus $2^k\,p\bmod r$ also is, thus $q=2^k\,p+1$ is divisible by $r$ with probability $1/(r-1)$, rather than $1/r$ for a random integer. It thus contributes to reducing the probability to be prime by a factor $\frac{r-2}{r-1}$ rather than $\frac{r-1}r$. We can correct for that effect, yielding $$\begin{align} \Pr(2^k\,p+1\text{ is prime})&\approx\frac2{\ln(p)+k\ln(2)}\ \prod_{r\in\Bbb P,\ 2<r<\sqrt p}\frac{r\,(r-2)}{(r-1)^2}\\ &\approx\frac{2\,C_2}{\ln(p)+k\ln(2)}\ \text{ with }C_2=0.66016\ldots \end{align}$$ since the product quickly converges to the twin prime constant $C_2$ (see A005597). That improved approximation is excellent for large $p$ as in the question.
We move to estimating the probability to find a prime $2^k\,p+1$ for a given $p$ and $k\in[k_0,k_1]$ with $k_0$ and $k_1$ close and commensurate with $\log_2(p)$.
As a crude approximation we can pretend that the probabilities to get a prime for one $k$ are independent of $k$, and approximate the probability that there is one prime $2^k\,p+1$ for $k\in[k_0,k_1]$ as the easily computed $$1-\prod_{k=k_0}^{k_1}\left(1-\frac{2\,C_2}{\ln(p)+k\ln(2)}\right)$$
For $p\approx 2^{256}$, $k\in[248,264]$ that gives a probability $0.061403\ldots$, meaning we'd need to test about one in $16.286\ldots$ primes $p$ to find a suitable one¹.
This approximation could likely be improved by taking into account that the probabilities for $2^k\,p+1$ to be divisible by a small prime $r$ for a given $p$ are strongly dependent on $k$, since $2^k\bmod r$ is a cyclic function of $k$, and worse of period $(r-1)/s$ often with $s\ge2$ (e.g. for $r=7$).
¹ What I got experimentally is close: $\frac{3395526}{208621}=16.27\ldots$ and $\frac{2116707}{130242}=16.25\ldots$ (scanning primes $p$ starting from $\left\lceil\frac7{22}\,\pi\,2^{256}\right\rceil$ and $\left\lceil\frac{113}{355}\,\pi\,2^{256}\right\rceil$ ).
This problem has been studied already; see this Wikipedia article.
Does there a exist a prime $q$ such that $p = 2^kq + 1$ is also prime?
A number $q$ such that $p$ is never prime is called a Sierpiński number; such numbers do exist, and some of them are prime. The smallest known such prime is $q = 271129$; the next known ones are $322523, 327739, 482719, 934909$.
I say "known" because there are several smaller primes where it is unknown whether they are Sierpiński numbers (that is, whether all values of the form $2^kq + 1$ are composite).
And, no, I don't have any great insight on, given $q$, how to find a prime $2^kq + 1$ (apart from the obvious "try various values of $k$, and check if results in a prime"); I do see that you could speed up the search slightly by tracking $q \bmod r$ for small $r$ (which would allow you to quickly eliminate values $2^kq + 1$ which are multiples of $r$ without explicitly computing the modulus)
