Let $p(k)$ be a complex polynomial of degree $n\in\mathbb{N}$. Let $A=\{k\in\mathbb{C}:\text{Re}\,p(k)=0\}$
The harmonic function $\text{Re}\,p(k)$ determines the behaviour of $A$. Fix $z\in A$. If atleast one of the partial derivatives $\partial_{\text{Re}\, k}\text{Re}\,p(z)$ or $\partial_{\text{Im}\, k}\text{Re}\,p(z)$ are not equal to zero, then the implicit function theorem gives that in every neighbourhood of such a point $z$, there exist a smooth curve such that $\text{Re}\,p=0$ on that curve in that neighbourhood. This only fails when both the partial derivatives are zero. But in the latter case due to Cauchy–Riemann equations $\frac{d}{dk}p(z)=0$ and this only occurs at a finite number of points.
Can someone help me describe what happens at a neighborhood of a point $z\in A$ where $\frac{d}{dk}p(z)=0$? Also is there some flaws in the above argument?
Your reasoning is correct. I think it's better to focus on the polynomial $p$ itself rather than its real part. You are considering the preimage of the imaginary axis under $p$.
In what follows, $p$ can be any holomorphic function, not necessarily a polynomial.
Two facts about holomorphic functions:
If $p'(a)\ne 0$, then $a$ has a neighborhood $U$ such that $p:U\to p(U)$ is a diffeomorphism. Hence $\{\operatorname{Re}p=0\}$ is an analytic curve near $a$.
Suppose $p'(a)=0$. Let $k$ be the smallest integer such that $p^{(k)}(a)\ne 0$. Then the Taylor expansion of $p$ about $a$ is $$p(z)-p(a) = c_{k} (z-a)^{k} +\dots = (z-a)^{k}q(z)$$ where $q$ is holomorphic and $q(a)\ne 0$. Let $g(z)=(z-a)q(z)^{1/k}$ (for some branch of fractional power; this is possible because $q(a)\ne 0$). Note that $g'(a)\ne 0$. Since $p = p(a) + g^k$, the part of the set $\{\operatorname{Re} p=0\}$ near $a$ is the preimage of the set $\{w:\operatorname{Re} w^k = 0 \}$ under $g$ (which is a diffeomorphism). That is, it is the union of $k$ analytic curves passing through $a$ and crossing at equal angles.
Example: $p(z)=z^3+z^4$, neighborhood of $0$.
Related post: Smoothness of level curves