Do you have to compute the nearest neighbours of all points, or just of a single point? And do you have to compute it/them once, or several times?
If you cannot assume anything about your points, then a spatial Octree is probably your best bet, cutting the space into eight equal cubes recursively until you have a small number of points per cell. You can look for neighbours of a point by inspecting all points in the same cell and successively climbing up the tree and inspecting neighbouring cells as you go.
If you can assume a maximum distance $r_c$ within which all $k$ neighbours will lie, then you could use a Cell List, which consists of partitioning the space into cells of edge length of at least $r_c$ in all dimensions. The neighbours of any given point will then be in any of the 26 cell surrounding that point's cell, so these are the only candidate points you need to consider. This approach is of course only useful if $r_c$ is reasonably bounded and if you are trying to find the neighbours of more than one point.
Dealing with boundary conditions is not much of an added difficulty, since in both cases you are dealing with cells of points which can be wrapped periodically.
Update
If you're only considering a single target point, you may be better off just computing the $k$ nearest brute-force.
If you have to compute the $k$ neighbours continuously, and the points only move by a bit, you can get some improvement by using a Verlet list (a.k.a. Neighbour list): Instead of finding the $k$ nearest neighbours, find the $K>k$ nearest. If $r_0$ is your target point, compute $s = \|r_0-r_K\| - \|r_0-r_k\|$, i.e. the difference in distance from the $k$th and $K$th nearest neighbours.
By doing this, in every iteration you only have to re-check these $K$ nearest neighbours and pick out the $k$ nearest. That is, until any of your points has moved more than $s$ since you first looked for the $K$ neighbours. If that happens, just re-start the whole procedure.
Update 2
You may already know this, but if you're aiming for efficiency, you should try using the Median of Medians algorithm to find the $k$ or $K$ smallest point distances.