Can one make statistical inferences from 6 patients? Is it conceptually correct to make statistical inferences from a very small number of patients (even when using exact methods like Fisher's test, etc)? What do I have to look out for: power or p-value?
 A: One thing you might want to do is figure out what the minimum p-value you could get for the tests you're considering for a sample size that small.  For example, with a total count of 6, the lowest p-value you can get for Fisher's test is 0.1.  So looking for a p-value < 0.05 in that case won't be fruitful.
It may be helpful to look at effect size statistics as well, such as phi, Cramér's V, or odds ratio for Fisher's test.  With a small sample size, you can't read too much into these statistics either, but they may more informative than p-values here.
### Example in R

Input =("
   Pass Fail
A   0    3
B   3    0
")

Matrix = as.matrix(read.table(textConnection(Input),
                   header=TRUE,
                   row.names=1))

Matrix

fisher.test(Matrix)

   ### Fisher's Exact Test for Count Data
   ### p-value = 0.1

   ### odds ratio 
   ###          0 


library(vcd)

assocstats(Matrix)

   ### Phi-Coefficient   : 1 

A: Yes, it is conceptually correct. But it is less likely that your results will be significant, and power will be small. 
What to look out for? I would look out for the quality of the sample first. Your results will tell you if there is anything significant, and you can always calculate the power for your given sample size to see what it is.
