What could be the negative factors in getting a PhD position in theoretical computer science? I have been searching and applying for funded PhD positions in Europe specially in Germany for a long time to no avail. I think, what pushes my applications back the most is the lack of proven prior research experience and also academic references. Each time I spend a good time researching the position and reading relevant publications and meticulously preparing my application. 

A brief background on me: got a course-based master's degree in CS (3 years ago) with a fairly good GPA (not top of the class, from a competitive university in my home country), familiar with major theoretical subjects (e.g approximation, CG, randomization etc.), 30 years old and +3 years work experience in industry.

I had no master's thesis but instead took more courses than a research-based program. Despite being confident that I can manage a research job well, still couldn't convince a single professor to choose me over other candidates.
I love algorithms and their analysis and I want to grow my knowledge deeper and contribute with my best hard work. But it seems to me that high motivation and a good background and potentials is not worthy and maybe a hard proof of prior research is necessary. Although I had few research activities, but they were no close to a full research which ends up with publications.

I quit a software development job in Germany only for the purpose of finding a PhD position. I find pure development soul sucking and short of the challenges like in CS and too mundane. I know at this point of life it's late (if not too late) to think of these stuff but you should know things are not normal in my country and I had a difficult life during my education, otherwise for sure I could have had a more appealing CV.

Here is the question. Could it be more than a lack of research experience? maybe my age and not looking fresh compared to recent graduates? could it be my works in industry?
For some reasons I feel there is something that depicts me not DESERVING the positions or tagging me as a tech enthusiast with little respect for theory.

I read other similar answers but they didn't quite match. This has become very frustrating and thinking of going back to basic coding jobs would be like throwing away all I strove for. There might be folks reading this with similar experience or those involved with candidate selection. Any help will be very much appreciated.
I have been in your situation, my first instinct tells me that you need to look into some developing jobs that pays and are challenging. So here are my couple of points:

How Well Is Your Personal Life?: I did obtained PhD in Computer Science and worked both as a lecturer and developer; and let me tell you that the "soul sucking" thing, needs to be deal with as a personal life solution and not professional. I did seen both academics and developers to be out of touch in personal wellness, and lived a very dark and sad life; that is nothing to do with what they are doing professionally. 

Age/Industry Isn't the Issue: While I was doing my PhD, a friend of mine who was 70 years old, built 2 software companies and sold them all, retired; and start doing PhD because feels like it. So, neither age or industry isn't a problem. 

What sort of developer? Ok, this might look funny but actually it is important to know what sort of software developer job you are doing? Were you dealing with old legacy software that you needed to maintained so it made you frustrated; or you were doing Web front-end stuff, which is a combination of taste and coding and not too much "science". If you are into logic related stuff, have you ever tried back-end development jobs? This is something you need to think about. 

Challenges As a Developer: You mentioned the developing jobs is not challenging. I was shocked! There are so many challenges today in industry, that people are trying to figure out. Look into cluster/distributed computing, containers, operating systems, wearable technologies and all their overall networking paradigms, and so on. You can also try to get some jobs which are challenging; so you could feel to void you are feeling, instead of spending the next year betting on being a lecturer. This brings me to the next point.

Lectureships: You might think, well I study couple of years as a PhD student and then Boom! I'm a lecturer in Germany or Europe. This is not true. Right now the trend in Europe is close to madness, to become a lecturer you should do some serious research, or coming from a huge research-based company (e.g., Google, etc.). Moreover, compare to industry, the payment is not very well; and the hours you have to put up with students, meetings, etc. are too much.